'다익스트라' 태그의 글 목록

[BOJ] 1238 파티 - Java

2024.04.18

✨ 그래프 👉 다익스트라 (최단경로 탐색 알고리즘) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 📍 고려해야할 점 각 학생들의 집에서 파티 장소까지 오고 가는 데 걸리는 최단 시간 구하기 도로들은 단방향 👉 길마다 걸리는 시간이 다르므로 오고 가는 길 또한 다름 ! N명의 학생들 중 오고 가는 데 가장 많은 시간을 소비한 학생 출력 🕹️ 풀이과정 집에서 파티 장소까지 가는 데 걸리는 최단 시간 + 파티 장소에서..

알고리즘/BOJ

[BOJ] 1504 특정한 최단 경로 - Java

2023.12.05

✨ 다익스트라 ➔ 최단경로 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 📍 고려해야할 점 방향이 없는 그래프이다. 1번 정점에서 N번 정점으로 최단거리로 이동한다. 주어진 두 정점을 반드시 거쳐야 한다. 두 정점이 v1, v2라면 1 ➔ v1 ➔ v2 ➔ N 또는 1 ➔ v2 ➔ v1 ➔ N 두가지 방법으로 이동할 수 있다. 🕹️ 풀이 방법 1️⃣ 노드에 대한 정보 (이동해야하는 노드 = v, 해..

알고리즘/BOJ

[BOJ] 18352 특정 거리의 도시 찾기 - Java

2023.12.04

✨ 그래프 탐색 ✨ BFS, 다익스트라 ➔ 최단 경로 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 📍 고려해야할 점 출발 도시에 대한 정보가 존재한다. 최단 거리에 대한 정보가 존재한다. ➔ 해당하는 최단 거리인 도시를 찾으면 된다. 하나의 도시에서 다른 모든 도시까지의 최단거리를 구해야하기 때문에 다익스트라 알고리즘을 사용한다. 도시간의 거리가 모두 1이기 때문..

알고리즘/🗂️ 정리

Dijkstra (다익스트라)

2023.03.03

DP(다이나믹 프로그래밍)를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 하나의 정점에서 다른 모든 정점까지의 최단거리를 구하는 문제에서 사용된다. 최단 거리는 여러 가지 최단 거리로 이루어져 있기 때문에 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하는 특징이 있다. 🕹️ 다익스트라 알고리즘 과정 출발 노드 설정 출발 노드를 기준으로 각 노드의 최소 비용 저장 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 해당 노드 거쳐서 특정한 노드로 가는 경우 고려하여 최소 비용 갱신 3️⃣, 4️⃣번 반복 기본적인 다익스트라 - 선형탐색 public class Main{ static int INF = 10000..

[BOJ] 1238 파티 - Java

[BOJ] 1504 특정한 최단 경로 - Java

[BOJ] 18352 특정 거리의 도시 찾기 - Java

Dijkstra (다익스트라)

티스토리툴바