์ถ์ฒ : https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7
์ต๋จ ๊ฒฝ๋ก
์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ์ฅ ์งง์ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ
์ ์๋ฏธํ๋ค.
๋ค์ํ ๋ฌธ์ ์ํฉ
โข ํ
์ง์ ์์ ๋ค๋ฅธ ํ
์ง์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก
โข ํ
์ง์ ์์ ๋ค๋ฅธ ๋ชจ๋
์ง์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก
โข ๋ชจ๋
์ง์ ์์ ๋ค๋ฅธ ๋ชจ๋
์ง์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก
๐๐ป ๊ฐ ์ง์
์ ๊ทธ๋ํ์์ ๋
ธ๋
๋ก ํํ
๐๐ป ์ง์ ๊ฐ ์ฐ๊ฒฐ๋ ๋๋ก
๋ ๊ทธ๋ํ์์ ๊ฐ์
์ผ๋ก ํํ
์ต๋จ ๊ฒฝ๋ก
๋ฅผ ๊ณ์ฐํ๋ค.๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ
์ผ๋ก ๋ถ๋ฅ๋๋ค.โ
๋ค๋ง ๊ธฐ๋ณธ์ ์ผ๋ก ์ต๋จ ๊ฒฝ๋ก ๋ฌธ์ ๋ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ ์๊ณ ๋ฆฌ์ฆ
์ผ๋ก ๋ถ๋ฅ๋๊ธฐ๋ ํ๋ค. A โก๏ธ C ๊น์ง ๊ฐ๋ ์ต๋จ ๊ฒฝ๋ก์ B๋ฅผ ๊ฑฐ์ณ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์กด์ฌํ๋ค๊ณ ํ๋ฉด A โก๏ธ B ์ต๋จ ๊ฒฝ๋ก์ B โก๏ธ C ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ณ ๋ คํด์ผํ๊ธฐ ๋๋ฌธ์ ๊ธฐ๋ณธ์ ์ผ๋ก ๊ธธ์ฐพ๊ธฐ ๋ฌธ์ ๋ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ ์๋ฆฌ๊ฐ ์ ์ฉ๋ ๋ฌธ์ ๋ผ๊ณ ํ ์ ์๋ค.
โ
ํ์ง๋ง ๋ค์ต์คํธ๋ผ ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ์ ํ์์ ์ธ ์๋ฆฌ๋ฅผ ์ด์ฉํ๋ฏ๋ก ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ
์ผ๋ก ๋ถ๋ฅ๋๋ค.
1๏ธโฃ ์ถ๋ฐ ๋
ธ๋๋ฅผ ์ค์ ํ๋ค.
2๏ธโฃ ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ์ด๊ธฐํํ๋ค. (์๊ธฐ ์์ ์ ๋ํ ๋
ธ๋๋ 0, ์์ โก๏ธ ์์ ์ต๋จ ๊ฒฝ๋ก๋ 0์ด๋ฏ๋ก)
3๏ธโฃ ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋
๋ฅผ ์ ํํ๋ค.
4๏ธโฃ ํด๋น ๋
ธ๋๋ฅผ ๊ฑฐ์ณ ๋ค๋ฅธ ๋
ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ ๊ณ์ฐํ์ฌ ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ๊ฐฑ์ ํ๋ค.
5๏ธโฃ ์ ๊ณผ์ ์์ 3๋ฒ๊ณผ 4๋ฒ์ ๋ฐ๋ณตํ๋ค.
์๊ณ ๋ฆฌ์ฆ ๋์ ๊ณผ์ ์์ ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ๊ฐ ๋
ธ๋์ ๋ํ ํ์ฌ๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ ์ ๋ณด๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ์ฒ๋ฆฌ ๊ณผ์ ์์ ๋ ์งง์ ๊ฒฝ๋ก๋ฅผ ์ฐพ์ผ๋ฉด '์ด์ ๋ถํฐ๋ ์ด ๊ฒฝ๋ก๊ฐ ์ ์ผ ์งง์ ๊ฒฝ๋ก์ผ' ๋ผ๊ณ ๊ฐฑ์ ํ๋ค.
โฌ๏ธ ๋ ์งง์ ๊ฒฝ๋ก๋ฅผ ์ฐพ์์ผ๋ฏ๋ก ๊ฐฑ์
๐ ๋์ ๊ณผ์ ์ดํด๋ณด๊ธฐ
[์ด๊ธฐ ์ํ] ๊ทธ๋ํ๋ฅผ ์ค๋นํ๊ณ ์ถ๋ฐ ๋
ธ๋๋ฅผ ์ค์ ํ๋ค.
[Step 1] ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋์ธ 1๋ฒ ๋
ธ๋
๋ฅผ ์ฒ๋ฆฌํ๋ค.
[Step 2] ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋์ธ 4๋ฒ ๋
ธ๋
๋ฅผ ์ฒ๋ฆฌํ๋ค.
[Step 3] ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋์ธ 2๋ฒ ๋
ธ๋
๋ฅผ ์ฒ๋ฆฌํ๋ค.
[Step 4] ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋์ธ 5๋ฒ ๋
ธ๋
๋ฅผ ์ฒ๋ฆฌํ๋ค.
[Step 5] ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋์ธ 3๋ฒ ๋
ธ๋
๋ฅผ ์ฒ๋ฆฌํ๋ค.
[Step 6] ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋์ธ 6๋ฒ ๋
ธ๋
๋ฅผ ์ฒ๋ฆฌํ๋ค. ์ฌ์ค ์ํ ์ํด๋ ๋๋ค. ๋ํ 6๋ฒ ๋
ธ๋์์ ์ถ๋ฐํ๋ ๊ฐ์ ์ด ์กด์ฌํ์ง ์์ ์ ์ด์ ํ
์ด๋ธ์ด ๊ฐฑ์ ๋์ง ์๋๋ค.
๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ
์ผ๋ก ๋ถ๋ฅ๋๋ค๋จ๊ณ๋ง๋ค ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋ ์ค์์ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋ ธ๋๋ฅผ ์ ํํ๊ธฐ ์ํด ๋งค ๋จ๊ณ๋ง๋ค 1์ฐจ์ ํ ์ด๋ธ์ ๋ชจ๋ ์์๋ฅผ ํ์ธ(์์ฐจ ํ์)ํ๋ค.
python
import sys input = sys.stdin.readline INF = int(1e9) # ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ # ๋ ธ๋์ ๊ฐ์, ๊ฐ์ ์ ๊ฐ์๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ n, m = map(int, input().split()) # ์์ ๋ ธ๋ ๋ฒํธ๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ start = int(input()) # ๊ฐ ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ graph = [[] for i in range(n + 1)] # ๋ฐฉ๋ฌธํ ์ ์ด ์๋์ง ์ฒดํฌํ๋ ๋ชฉ์ ์ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ visited = [False] * (n + 1) # ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ distance = [INF] * (n + 1) # ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ for _ in range(m): a, b, c = map(int, input().split()) # a๋ฒ ๋ ธ๋์์ b๋ฒ ๋ ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ด c๋ผ๋ ์๋ฏธ graph[a].append((b, c)) # ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋ ์ค์์, ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋ ธ๋์ ๋ฒํธ๋ฅผ ๋ฐํ def get_smallest_node(): min_value = INF index = 0 # ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋ ธ๋(์ธ๋ฑ์ค) for i in range(1, n + 1): if distance[i] < min_value and not visited[i]: min_value = distance[i] index = i return index def dijkstra(start): # ์์ ๋ ธ๋์ ๋ํด์ ์ด๊ธฐํ distance[start] = 0 visited[start] = True for j in graph[start]: distance[j[0]] = j[1] # ์์ ๋ ธ๋๋ฅผ ์ ์ธํ ์ ์ฒด n - 1๊ฐ์ ๋ ธ๋์ ๋ํด ๋ฐ๋ณต for i in range(n - 1): # ํ์ฌ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋ ธ๋๋ฅผ ๊บผ๋ด์, ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ now = get_smallest_node() visited[now] = True # ํ์ฌ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋ ธ๋๋ฅผ ํ์ธ for j in graph[now]: cost = distance[now] + j[1] # ํ์ฌ ๋ ธ๋๋ฅผ ๊ฑฐ์ณ์ ๋ค๋ฅธ ๋ ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ if cost < distance[j[0]]: distance[j[0]] = cost # ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ dijkstra(start) # ๋ชจ๋ ๋ ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ for i in range(1, n + 1): # ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, ๋ฌดํ(INFINITY)์ด๋ผ๊ณ ์ถ๋ ฅ if distance[i] == INF: print("INFINITY") # ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ else: print(distance[i])
Java
import java.util.*; class Node { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getIndex() { return this.index; } public int getDistance() { return this.distance; } } public class Main { public static final int INF = (int) 1e9; // ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ // ๋ ธ๋์ ๊ฐ์(N), ๊ฐ์ ์ ๊ฐ์(M), ์์ ๋ ธ๋ ๋ฒํธ(Start) // ๋ ธ๋์ ๊ฐ์๋ ์ต๋ 100,000๊ฐ๋ผ๊ณ ๊ฐ์ public static int n, m, start; // ๊ฐ ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฐฐ์ด public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>(); // ๋ฐฉ๋ฌธํ ์ ์ด ์๋์ง ์ฒดํฌํ๋ ๋ชฉ์ ์ ๋ฐฐ์ด ๋ง๋ค๊ธฐ public static boolean[] visited = new boolean[100001]; // ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ ๋ง๋ค๊ธฐ public static int[] d = new int[100001]; // ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋ ์ค์์, ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋ ธ๋์ ๋ฒํธ๋ฅผ ๋ฐํ public static int getSmallestNode() { int min_value = INF; int index = 0; // ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋ ธ๋(์ธ๋ฑ์ค) for (int i = 1; i <= n; i++) { if (d[i] < min_value && !visited[i]) { min_value = d[i]; index = i; } } return index; } public static void dijkstra(int start) { // ์์ ๋ ธ๋์ ๋ํด์ ์ด๊ธฐํ d[start] = 0; visited[start] = true; for (int j = 0; j < graph.get(start).size(); j++) { d[graph.get(start).get(j).getIndex()] = graph.get(start).get(j).getDistance(); } // ์์ ๋ ธ๋๋ฅผ ์ ์ธํ ์ ์ฒด n - 1๊ฐ์ ๋ ธ๋์ ๋ํด ๋ฐ๋ณต for (int i = 0; i < n - 1; i++) { // ํ์ฌ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋ ธ๋๋ฅผ ๊บผ๋ด์, ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ int now = getSmallestNode(); visited[now] = true; // ํ์ฌ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋ ธ๋๋ฅผ ํ์ธ for (int j = 0; j < graph.get(now).size(); j++) { int cost = d[now] + graph.get(now).get(j).getDistance(); // ํ์ฌ ๋ ธ๋๋ฅผ ๊ฑฐ์ณ์ ๋ค๋ฅธ ๋ ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ if (cost < d[graph.get(now).get(j).getIndex()]) { d[graph.get(now).get(j).getIndex()] = cost; } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); start = sc.nextInt(); // ๊ทธ๋ํ ์ด๊ธฐํ for (int i = 0; i <= n; i++) { graph.add(new ArrayList<Node>()); } // ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ for (int i = 0; i < m; i++) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); // a๋ฒ ๋ ธ๋์์ b๋ฒ ๋ ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ด c๋ผ๋ ์๋ฏธ graph.get(a).add(new Node(b, c)); } // ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ Arrays.fill(d, INF); // ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ dijkstra(start); // ๋ชจ๋ ๋ ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ for (int i = 1; i <= n; i++) { // ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, ๋ฌดํ(INFINITY)์ด๋ผ๊ณ ์ถ๋ ฅ if (d[i] == INF) { System.out.println("INFINITY"); } // ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ else { System.out.println(d[i]); } } } }
์ฑ๋ฅ ๋ถ์
์ด 0(V)
๋ฒ์ ๊ฑธ์ณ์ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋๋ฅผ ๋งค๋ฒ ์ ํ ํ์ํด์ผ ํ๋ฏ๋ก ์ ์ฒด ์๊ฐ ๋ณต์ก๋๋ 0(V^2)
์ด๋ค.
์ผ๋ฐ์ ์ผ๋ก ์ฝ๋ฉ ํ
์คํธ์ ์ต๋จ ๊ฒฝ๋ก ๋ฌธ์ ์์ ์ ์ฒด ๋
ธ๋์ ๊ฐ์๊ฐ 5,000๊ฐ ์ดํ
๋ผ๋ฉด ์ด ์ฝ๋๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
ํ์ง๋ง ๋
ธ๋์ ๊ฐ์๊ฐ 10,000๊ฐ
๋ฅผ ๋์ด๊ฐ๋ ๋ฌธ์ ๋ผ๋ฉด โ 1์ต์ด ๋๋ ์ฐ์ฐ์ ์ํํด์ผ ํ ๊ฒ์ด๋ค. ๋ฐ๋ผ์ ์ฐ๋ฆฌ๋ ์ฐ์ ์์ ํ
์ ๋ํด ์์๋ณผ ํ์๊ฐ ์๋ค.
ํ์ค ๋ผ์ด๋ธ๋ฌ๋ฆฌ
ํํ๋ก ์ง์ํ๋ค.์ต์ ํ(Min Heap)
๊ณผ ์ต๋ ํ(Max Heap)
์ด ์๋ค.์ต์ ํ(Min Heap)
์ ๊ฐ์ด ๋ฎ์ ๋ฐ์ดํฐ๋ถํฐ ์ถ์ถํ๋ ๋ฐฉ์์ด๊ณ ์ต๋ ํ(Max Heap)
์ ๊ฐ์ด ๋์ ๋ฐ์ดํฐ๋ถํฐ ์ถ์ถํ๋ ๋ฐฉ์์ด๋ค.๐๐ป ์๊ฐ ๋ณต์ก๋๊ฐ ๋ฆฌ์คํธ์ ๋นํด O(logN)
์ด๊ธฐ ๋๋ฌธ์ ํจ์ฌ ํจ๊ณผ์ ์ด๋ค.
์ต์ํ
import heapq # ์ค๋ฆ์ฐจ์ ํ ์ ๋ ฌ(Heap Sort) def heapsort(iterable): h = [] result = [] # ๋ชจ๋ ์์๋ฅผ ์ฐจ๋ก๋๋ก ํ์ ์ฝ์ for value in iterable: heapq.heappush(h, value) # ํ์ ์ฝ์ ๋ ๋ชจ๋ ์์๋ฅผ ์ฐจ๋ก๋๋ก ๊บผ๋ด์ด ๋ด๊ธฐ for i in range(len(h)): result.append(heapq.heappop(h)) return result result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) print(result) # ๊ฒฐ๊ณผ : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
์ต๋ํ
import heapq # ๋ด๋ฆผ์ฐจ์ ํ ์ ๋ ฌ(Heap Sort) def heapsort(iterable): h = [] result = [] # ๋ชจ๋ ์์๋ฅผ ์ฐจ๋ก๋๋ก ํ์ ์ฝ์ for value in iterable: heapq.heappush(h, -value) # ๋ถํธ๋ฅผ ๋ฐ๊ฟ์ ๋ฃ์ด์ค # ํ์ ์ฝ์ ๋ ๋ชจ๋ ์์๋ฅผ ์ฐจ๋ก๋๋ก ๊บผ๋ด์ด ๋ด๊ธฐ for i in range(len(h)): result.append(-heapq.heappop(h)) # ๋ถํธ๋ฅผ ๋ฐ๊ฟ์ ์ฝ์ return result result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) print(result) # ๊ฒฐ๊ณผ : [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
ํ(Heap)
์๋ฃ๊ตฌ์กฐ๋ฅผ ์ด์ฉํ๋ค.์ต์ ํ
์ ์ฌ์ฉํ๋ค.[์ด๊ธฐ ์ํ] ๊ทธ๋ํ๋ฅผ ์ค๋นํ๊ณ ์ถ๋ฐ ๋
ธ๋๋ฅผ ์ค์ ํ์ฌ ์ฐ์ ์์ ํ์ ์ฝ์
ํฉ๋๋ค. 1 ์์ 1 ๊น์ง๋ 0์ด๋ฏ๋ก ๊ฑฐ๋ฆฌ๋ 0์ด๋ค.
[Step 1] ์ฐ์ ์์ ํ์์ ์์๋ฅผ ๊บผ๋ ๋๋ค. 1๋ฒ ๋ ธ๋๋ ์์ง ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฏ๋ก ์ด๋ฅผ ์ฒ๋ฆฌํฉ๋๋ค. ๋ํ ๊ฑฐ์ณ๊ฐ ๋์ ๊ฐ์ด ํ์ฌ ๊ฐ๋ณด๋ค ์์ผ๋ฏ๋ก ํ ์ด๋ธ์ ๊ฐฑ์ ํด์ค๋ค. ๋ํ ๊ฐฑ์ ๋ ๋๋ง ํ์ ํด๋น ๊ฐฑ์ ๋ ๋ ธ๋์ ์ ๋ณด๋ฅผ ๋ด์์ค๋ค.
๊ทธ๋ฆผ์ ์ฐ์ ์์๊ฐ ๋์ ๋ฐ์ดํฐ๊ฐ ์์ชฝ์ ๋ค์ด๊ฐ ์ ์๋๋ก ๊ทธ๋ ค์ฃผ์๋ค.
[Step 2] ์ฐ์ ์์ ํ์์ ์์(ํ ์ ์ผ ์์ ์๋ 4๋ฒ ๋
ธ๋)๋ฅผ ๊บผ๋
๋๋ค. 4๋ฒ ๋
ธ๋๋ ์์ง ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฏ๋ก ์ด๋ฅผ ์ฒ๋ฆฌํฉ๋๋ค. ๋
ธ๋ 4๋ฅผ ๊ฑฐ์ณ๊ฐ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ธํ์ฌ 3์ผ๋ก ๊ฐ๋ ๋น์ฉ(1 -> 4 -> 3)๊ณผ 5(1 -> 4 -> 5)๋ก ๊ฐ๋ ๋น์ฉ์ ๊ณ์ฐํ ํ ๊ฐฑ์ ํฉ๋๋ค.
[Step 3] ์ฐ์ ์์ ํ์์ ์์๋ฅผ ๊บผ๋
๋๋ค. 2๋ฒ ๋
ธ๋๋ ์์ง ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฏ๋ก ์ด๋ฅผ ์ฒ๋ฆฌํฉ๋๋ค. ๋
ธ๋ 2๋ฅผ ๊ฑฐ์ณ๊ฐ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ธํ์ฌ 3์ผ๋ก ๊ฐ๋ ๋น์ฉ(1 -> 2 -> 3)๊ณผ 4(1 -> 2 -> 4)๋ก ๊ฐ๋ ๋น์ฉ์ ๊ณ์ฐ ํ ๊ฐฑ์ ํ๋ ค ํ์ง๋ง ์๋ ๊ฐ๋ณด๋ค ํฌ๋ฏ๋ก ๊ฐฑ์ ํ์ง ์์ต๋๋ค. ๋ฐ๋ผ์ ํ
์ด๋ธ๊ณผ ์ฐ์ ์์ ํ ๋ํ ๋ฐ๋์ง ์์ต๋๋ค.
[Step 4] ์ฐ์ ์์ ํ์์ ์์๋ฅผ ๊บผ๋
๋๋ค. 5๋ฒ ๋
ธ๋๋ ์์ง ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฏ๋ก ์ด๋ฅผ ์ฒ๋ฆฌํฉ๋๋ค. 5๊น์ง์ ์ต์ ๋น์ฉ์ด 1 + 1 = 2๋ก ๊ฐฑ์ ๋๊ณ , ์ฐ๊ฒฐ๋ ๋
ธ๋์ธ 3๊ณผ 6์ ์ต์ ๋น์ฉ๋ํ ๊ฐฑ์ ๋๋ค.
[Step 5] ์ฐ์ ์์ ํ์์ ์์๋ฅผ ๊บผ๋
๋๋ค. 3๋ฒ ๋
ธ๋๋ ์์ง ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฏ๋ก ์ด๋ฅผ ์ฒ๋ฆฌํฉ๋๋ค.
[Step 6] ์ฐ์ ์์ ํ์์ ์์๋ฅผ ๊บผ๋
๋๋ค. 3๋ฒ ๋
ธ๋๋ ์ด๋ฏธ ๋ฐฉ๋ฌธํ์ผ๋ฏ๋ก ๋ฌด์ํฉ๋๋ค.
[Step 7] ์ฐ์ ์์ ํ์์ ์์๋ฅผ ๊บผ๋
๋๋ค. 6๋ฒ ๋
ธ๋๋ ์์ง ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฏ๋ก ์ด๋ฅผ ์ฒ๋ฆฌํฉ๋๋ค.
[Step 8] ์ฐ์ ์์ ํ์์ ์์๋ฅผ ๊บผ๋
๋๋ค. 3๋ฒ ๋
ธ๋๋ ์ด๋ฏธ ๋ฐฉ๋ฌธํ์ผ๋ฏ๋ก ๋ฌด์ํฉ๋๋ค. ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ ํ
์ด๋ธ์ ์๋ ๊ฐ๋ณด๋ค ๊บผ๋ธ ์์์ ๊ฐ์ด ๋ ํฌ๋ค๋ฉด ๋ฐฉ๋ฌธํ ๊ฒ์ผ๋ก ๊ฐ์ฃผํ๋ค.
python
import heapq import sys input = sys.stdin.readline INF = int(1e9) # ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ # ๋ ธ๋์ ๊ฐ์, ๊ฐ์ ์ ๊ฐ์๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ n, m = map(int, input().split()) # ์์ ๋ ธ๋ ๋ฒํธ๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ start = int(input()) # ๊ฐ ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ graph = [[] for i in range(n + 1)] # ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ distance = [INF] * (n + 1) # ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ for _ in range(m): a, b, c = map(int, input().split()) # a๋ฒ ๋ ธ๋์์ b๋ฒ ๋ ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ด c๋ผ๋ ์๋ฏธ graph[a].append((b, c)) def dijkstra(start): q = [] # ์์ ๋ ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฒฝ๋ก๋ 0์ผ๋ก ์ค์ ํ์ฌ, ํ์ ์ฝ์ heapq.heappush(q, (0, start)) distance[start] = 0 while q: # ํ๊ฐ ๋น์ด์์ง ์๋ค๋ฉด # ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋ ธ๋์ ๋ํ ์ ๋ณด ๊บผ๋ด๊ธฐ dist, now = heapq.heappop(q) # ํ์ฌ ๋ ธ๋๊ฐ ์ด๋ฏธ ์ฒ๋ฆฌ๋ ์ ์ด ์๋ ๋ ธ๋๋ผ๋ฉด ๋ฌด์ if distance[now] < dist: continue # ํ์ฌ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ์ธ์ ํ ๋ ธ๋๋ค์ ํ์ธ for i in graph[now]: cost = dist + i[1] # ํ์ฌ ๋ ธ๋๋ฅผ ๊ฑฐ์ณ์, ๋ค๋ฅธ ๋ ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) # ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ dijkstra(start) # ๋ชจ๋ ๋ ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ for i in range(1, n + 1): # ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, ๋ฌดํ(INFINITY)์ด๋ผ๊ณ ์ถ๋ ฅ if distance[i] == INF: print("INFINITY") # ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ else: print(distance[i])
Java
import java.util.*; class Node implements Comparable<Node> { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getIndex() { return this.index; } public int getDistance() { return this.distance; } // ๊ฑฐ๋ฆฌ(๋น์ฉ)๊ฐ ์งง์ ๊ฒ์ด ๋์ ์ฐ์ ์์๋ฅผ ๊ฐ์ง๋๋ก ์ค์ @Override public int compareTo(Node other) { if (this.distance < other.distance) { return -1; } return 1; } } public class Main { public static final int INF = (int) 1e9; // ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ // ๋ ธ๋์ ๊ฐ์(N), ๊ฐ์ ์ ๊ฐ์(M), ์์ ๋ ธ๋ ๋ฒํธ(Start) // ๋ ธ๋์ ๊ฐ์๋ ์ต๋ 100,000๊ฐ๋ผ๊ณ ๊ฐ์ public static int n, m, start; // ๊ฐ ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฐฐ์ด public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>(); // ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ ๋ง๋ค๊ธฐ public static int[] d = new int[100001]; public static void dijkstra(int start) { PriorityQueue<Node> pq = new PriorityQueue<>(); // ์์ ๋ ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฒฝ๋ก๋ 0์ผ๋ก ์ค์ ํ์ฌ, ํ์ ์ฝ์ pq.offer(new Node(start, 0)); d[start] = 0; while(!pq.isEmpty()) { // ํ๊ฐ ๋น์ด์์ง ์๋ค๋ฉด // ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋ ธ๋์ ๋ํ ์ ๋ณด ๊บผ๋ด๊ธฐ Node node = pq.poll(); int dist = node.getDistance(); // ํ์ฌ ๋ ธ๋๊น์ง์ ๋น์ฉ int now = node.getIndex(); // ํ์ฌ ๋ ธ๋ // ํ์ฌ ๋ ธ๋๊ฐ ์ด๋ฏธ ์ฒ๋ฆฌ๋ ์ ์ด ์๋ ๋ ธ๋๋ผ๋ฉด ๋ฌด์ if (d[now] < dist) continue; // ํ์ฌ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ์ธ์ ํ ๋ ธ๋๋ค์ ํ์ธ for (int i = 0; i < graph.get(now).size(); i++) { int cost = d[now] + graph.get(now).get(i).getDistance(); // ํ์ฌ ๋ ธ๋๋ฅผ ๊ฑฐ์ณ์, ๋ค๋ฅธ ๋ ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ if (cost < d[graph.get(now).get(i).getIndex()]) { d[graph.get(now).get(i).getIndex()] = cost; pq.offer(new Node(graph.get(now).get(i).getIndex(), cost)); } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); start = sc.nextInt(); // ๊ทธ๋ํ ์ด๊ธฐํ for (int i = 0; i <= n; i++) { graph.add(new ArrayList<Node>()); } // ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ for (int i = 0; i < m; i++) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); // a๋ฒ ๋ ธ๋์์ b๋ฒ ๋ ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ด c๋ผ๋ ์๋ฏธ graph.get(a).add(new Node(b, c)); } // ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ Arrays.fill(d, INF); // ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ dijkstra(start); // ๋ชจ๋ ๋ ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ for (int i = 1; i <= n; i++) { // ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, ๋ฌดํ(INFINITY)์ด๋ผ๊ณ ์ถ๋ ฅ if (d[i] == INF) { System.out.println("INFINITY"); } // ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ else { System.out.println(d[i]); } } } }
์ฑ๋ฅ ๋ถ์
O(ElogV)
์ด๋ค.O(ElogE)
๋ก ํ๋จํ ์ ์๋ค.O(ElogV)
๋ก ์ ๋ฆฌํ ์ ์๋ค.
O(ElogE)
โก๏ธO(ElogV^2)
โก๏ธO(2ElogV)
โก๏ธO(ElogV)
์ต๋จ ๊ฒฝ๋ก
๋ฅผ ๋ชจ๋ ๊ณ์ฐํ๋ค.๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
์ ํ์ ์ํ๋ค.์ ํ์์ ์๋๊ณผ ๊ฐ๋ค.
[์ด๊ธฐ ์ํ] ๊ทธ๋ํ๋ฅผ ์ค๋นํ๊ณ ์ธ์ ํ ๋
ธ๋๋ง ํ์ธํด์ ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ์ด๊ธฐํํ๋ค. ์ด๋, ํ = ์ถ๋ฐ๋
ธ๋, ์ด = ๋์ฐฉ ๋
ธ๋๋ฅผ ์๋ฏธํ๋ค.
[STEP 1] 1๋ฒ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ ๊ฐ๋ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ์ฌ ํ
์ด๋ธ์ ๊ฐฑ์ ํ๋ค.
0 : ์๊ธฐ ์์ โก๏ธ ์๊ธฐ ์์ ์ธ ๊ฒฝ์ฐ
[STEP 2] 2๋ฒ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ ๊ฐ๋ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ์ฌ ํ
์ด๋ธ์ ๊ฐฑ์ ํ๋ค.
[STEP 3] 3๋ฒ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ ๊ฐ๋ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ์ฌ ํ
์ด๋ธ์ ๊ฐฑ์ ํ๋ค.
[STEP 4] 4๋ฒ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ ๊ฐ๋ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ์ฌ ํ
์ด๋ธ์ ๊ฐฑ์ ํ๋ค.
python
INF = int(1e9) # ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ # ๋ ธ๋์ ๊ฐ์ ๋ฐ ๊ฐ์ ์ ๊ฐ์๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ n = int(input()) m = int(input()) # 2์ฐจ์ ๋ฆฌ์คํธ(๊ทธ๋ํ ํํ)๋ฅผ ๋ง๋ค๊ณ , ๋ชจ๋ ๊ฐ์ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ graph = [[INF] * (n + 1) for _ in range(n + 1)] # ์๊ธฐ ์์ ์์ ์๊ธฐ ์์ ์ผ๋ก ๊ฐ๋ ๋น์ฉ์ 0์ผ๋ก ์ด๊ธฐํ for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0 # ๊ฐ ๊ฐ์ ์ ๋ํ ์ ๋ณด๋ฅผ ์ ๋ ฅ ๋ฐ์, ๊ทธ ๊ฐ์ผ๋ก ์ด๊ธฐํ for _ in range(m): # A์์ B๋ก ๊ฐ๋ ๋น์ฉ์ C๋ผ๊ณ ์ค์ a, b, c = map(int, input().split()) graph[a][b] = c # ์ ํ์์ ๋ฐ๋ผ ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ ์ํ for k in range(1, n + 1): for a in range(1, n + 1): for b in range(1, n + 1): graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) # ์ํ๋ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅ for a in range(1, n + 1): for b in range(1, n + 1): # ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, ๋ฌดํ(INFINITY)์ด๋ผ๊ณ ์ถ๋ ฅ if graph[a][b] == 1e9: print("INFINITY", end=" ") # ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ else: print(graph[a][b], end=" ") print()
Java
import java.util.*; public class Main { public static final int INF = (int) 1e9; // ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ // ๋ ธ๋์ ๊ฐ์(N), ๊ฐ์ ์ ๊ฐ์(M) // ๋ ธ๋์ ๊ฐ์๋ ์ต๋ 500๊ฐ๋ผ๊ณ ๊ฐ์ public static int n, m; // 2์ฐจ์ ๋ฐฐ์ด(๊ทธ๋ํ ํํ)๋ฅผ ๋ง๋ค๊ธฐ public static int[][] graph = new int[501][501]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); // ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ for (int i = 0; i < 501; i++) { Arrays.fill(graph[i], INF); } // ์๊ธฐ ์์ ์์ ์๊ธฐ ์์ ์ผ๋ก ๊ฐ๋ ๋น์ฉ์ 0์ผ๋ก ์ด๊ธฐํ for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { if (a == b) graph[a][b] = 0; } } // ๊ฐ ๊ฐ์ ์ ๋ํ ์ ๋ณด๋ฅผ ์ ๋ ฅ ๋ฐ์, ๊ทธ ๊ฐ์ผ๋ก ์ด๊ธฐํ for (int i = 0; i < m; i++) { // A์์ B๋ก ๊ฐ๋ ๋น์ฉ์ C๋ผ๊ณ ์ค์ int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); graph[a][b] = c; } // ์ ํ์์ ๋ฐ๋ผ ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ ์ํ for (int k = 1; k <= n; k++) { for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]); } } } // ์ํ๋ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅ for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { // ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, ๋ฌดํ(INFINITY)์ด๋ผ๊ณ ์ถ๋ ฅ if (graph[a][b] == INF) { System.out.print("INFINITY "); } // ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ else { System.out.print(graph[a][b] + " "); } } System.out.println(); } } }
์ฑ๋ฅ ๋ถ์
O(N^2)
์ ์ฐ์ฐ์ ํตํด ํ์ฌ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ ๊ฐ๋ ๋ชจ๋ ๊ฒฝ๋ก๋ฅผ ๊ณ ๋ คํ๋ค.O(N^3)
์ด๋ค.500๊ฐ
์ดํ ์ ๋๋ก ์์ ๊ฒฝ์ฐ์๋ง ํ๋ ๊ฒ์ด ์ข๋ค. ๋ฐฉํฅ์ฑ
์ด ์๋ ๊ทธ๋ํ์ต๋จ ๊ฑฐ๋ฆฌ ๋ฌธ์
๋ก ์นํํ ์ ์๋ค.๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ
์ ๊ตฌํํ๋ค.
python
import heapq import sys input = sys.stdin.readline INF = int(1e9) # ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ # ๋ ธ๋์ ๊ฐ์, ๊ฐ์ ์ ๊ฐ์, ์์ ๋ ธ๋๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ n, m, start = map(int, input().split()) # ๊ฐ ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ graph = [[] for i in range(n + 1)] # ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ distance = [INF] * (n + 1) # ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ for _ in range(m): x, y, z = map(int, input().split()) # X๋ฒ ๋ ธ๋์์ Y๋ฒ ๋ ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ด Z๋ผ๋ ์๋ฏธ graph[x].append((y, z)) def dijkstra(start): q = [] # ์์ ๋ ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฒฝ๋ก๋ 0์ผ๋ก ์ค์ ํ์ฌ, ํ์ ์ฝ์ heapq.heappush(q, (0, start)) distance[start] = 0 while q: # ํ๊ฐ ๋น์ด์์ง ์๋ค๋ฉด # ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋ ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๊บผ๋ด๊ธฐ dist, now = heapq.heappop(q) if distance[now] < dist: continue # ํ์ฌ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ์ธ์ ํ ๋ ธ๋๋ค์ ํ์ธ for i in graph[now]: cost = dist + i[1] # ํ์ฌ ๋ ธ๋๋ฅผ ๊ฑฐ์ณ์, ๋ค๋ฅธ ๋ ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) # ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ dijkstra(start) # ๋๋ฌํ ์ ์๋ ๋ ธ๋์ ๊ฐ์ count = 0 # ๋๋ฌํ ์ ์๋ ๋ ธ๋ ์ค์์, ๊ฐ์ฅ ๋ฉ๋ฆฌ ์๋ ๋ ธ๋์์ ์ต๋จ ๊ฑฐ๋ฆฌ max_distance = 0 for d in distance: # ๋๋ฌํ ์ ์๋ ๋ ธ๋์ธ ๊ฒฝ์ฐ if d != 1e9: count += 1 max_distance = max(max_distance, d) # ์์ ๋ ธ๋๋ ์ ์ธํด์ผ ํ๋ฏ๋ก count - 1์ ์ถ๋ ฅ print(count - 1, max_distance)
Java
import java.util.*; class Node implements Comparable<Node> { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getIndex() { return this.index; } public int getDistance() { return this.distance; } // ๊ฑฐ๋ฆฌ(๋น์ฉ)๊ฐ ์งง์ ๊ฒ์ด ๋์ ์ฐ์ ์์๋ฅผ ๊ฐ์ง๋๋ก ์ค์ @Override public int compareTo(Node other) { if (this.distance < other.distance) { return -1; } return 1; } } public class Main { public static final int INF = (int) 1e9; // ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ // ๋ ธ๋์ ๊ฐ์(N), ๊ฐ์ ์ ๊ฐ์(M), ์์ ๋ ธ๋ ๋ฒํธ(Start) public static int n, m, start; // ๊ฐ ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฐฐ์ด public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>(); // ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ ๋ง๋ค๊ธฐ public static int[] d = new int[30001]; public static void dijkstra(int start) { PriorityQueue<Node> pq = new PriorityQueue<>(); // ์์ ๋ ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฒฝ๋ก๋ 0์ผ๋ก ์ค์ ํ์ฌ, ํ์ ์ฝ์ pq.offer(new Node(start, 0)); d[start] = 0; while(!pq.isEmpty()) { // ํ๊ฐ ๋น์ด์์ง ์๋ค๋ฉด // ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋ ธ๋์ ๋ํ ์ ๋ณด ๊บผ๋ด๊ธฐ Node node = pq.poll(); int dist = node.getDistance(); // ํ์ฌ ๋ ธ๋๊น์ง์ ๋น์ฉ int now = node.getIndex(); // ํ์ฌ ๋ ธ๋ // ํ์ฌ ๋ ธ๋๊ฐ ์ด๋ฏธ ์ฒ๋ฆฌ๋ ์ ์ด ์๋ ๋ ธ๋๋ผ๋ฉด ๋ฌด์ if (d[now] < dist) continue; // ํ์ฌ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ์ธ์ ํ ๋ ธ๋๋ค์ ํ์ธ for (int i = 0; i < graph.get(now).size(); i++) { int cost = d[now] + graph.get(now).get(i).getDistance(); // ํ์ฌ ๋ ธ๋๋ฅผ ๊ฑฐ์ณ์, ๋ค๋ฅธ ๋ ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ if (cost < d[graph.get(now).get(i).getIndex()]) { d[graph.get(now).get(i).getIndex()] = cost; pq.offer(new Node(graph.get(now).get(i).getIndex(), cost)); } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); start = sc.nextInt(); // ๊ทธ๋ํ ์ด๊ธฐํ for (int i = 0; i <= n; i++) { graph.add(new ArrayList<Node>()); } // ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ for (int i = 0; i < m; i++) { int x = sc.nextInt(); int y = sc.nextInt(); int z = sc.nextInt(); // X๋ฒ ๋ ธ๋์์ Y๋ฒ ๋ ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ด Z๋ผ๋ ์๋ฏธ graph.get(x).add(new Node(y, z)); } // ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ Arrays.fill(d, INF); // ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ dijkstra(start); // ๋๋ฌํ ์ ์๋ ๋ ธ๋์ ๊ฐ์ int count = 0; // ๋๋ฌํ ์ ์๋ ๋ ธ๋ ์ค์์, ๊ฐ์ฅ ๋ฉ๋ฆฌ ์๋ ๋ ธ๋์์ ์ต๋จ ๊ฑฐ๋ฆฌ int maxDistance = 0; for (int i = 1; i <= n; i++) { // ๋๋ฌํ ์ ์๋ ๋ ธ๋์ธ ๊ฒฝ์ฐ if (d[i] != INF) { count += 1; maxDistance = Math.max(maxDistance, d[i]); } } // ์์ ๋ ธ๋๋ ์ ์ธํด์ผ ํ๋ฏ๋ก count - 1์ ์ถ๋ ฅ System.out.println((count - 1) + " " + maxDistance); } }
๋ฐฉํฅ์ฑ
์ด ์๋ ์๋ฐฉํฅ ๊ทธ๋ํ1
๋งํผ์ ์๊ฐ์ต๋จ ๊ฑฐ๋ฆฌ
๋ฌธ์ ์ด๋ฏ๋ก ์ต๋จ ๊ฑฐ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด ํด๊ฒฐํ๋ค.ํ๋ก์ด๋ ์์
์๊ณ ๋ฆฌ์ฆ
์ ์ด์ฉํด๋ ํจ์จ์ ์ผ๋ก ํด๊ฒฐํ ์ ์๋ค.ํ๋ก์ด๋ ์์
์๊ณ ๋ฆฌ์ฆ
์ ์ํํ ๋ค์ (1๋ฒ ๋
ธ๋์์ X๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ + X์์ K๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ)๋ฅผ ๊ณ์ฐํ์ฌ ์ถ๋ ฅํ๋ฉด ์ ๋ต ํ์ ์ ๋ฐ์ ์ ์๋ค.
python
INF = int(1e9) # ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ # ๋ ธ๋์ ๊ฐ์ ๋ฐ ๊ฐ์ ์ ๊ฐ์๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ n, m = map(int, input().split()) # 2์ฐจ์ ๋ฆฌ์คํธ(๊ทธ๋ํ ํํ)๋ฅผ ๋ง๋ค๊ณ , ๋ชจ๋ ๊ฐ์ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ graph = [[INF] * (n + 1) for _ in range(n + 1)] # ์๊ธฐ ์์ ์์ ์๊ธฐ ์์ ์ผ๋ก ๊ฐ๋ ๋น์ฉ์ 0์ผ๋ก ์ด๊ธฐํ for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0 # ๊ฐ ๊ฐ์ ์ ๋ํ ์ ๋ณด๋ฅผ ์ ๋ ฅ ๋ฐ์, ๊ทธ ๊ฐ์ผ๋ก ์ด๊ธฐํ for _ in range(m): # A์ B๊ฐ ์๋ก์๊ฒ ๊ฐ๋ ๋น์ฉ์ 1์ด๋ผ๊ณ ์ค์ a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 # ๊ฑฐ์ณ ๊ฐ ๋ ธ๋ X์ ์ต์ข ๋ชฉ์ ์ง ๋ ธ๋ K๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ x, k = map(int, input().split()) # ์ ํ์์ ๋ฐ๋ผ ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ ์ํ for k in range(1, n + 1): for a in range(1, n + 1): for b in range(1, n + 1): graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) # ์ํ๋ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅ distance = graph[1][k] + graph[k][x] # ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, -1์ ์ถ๋ ฅ if distance >= 1e9: print("-1") # ๋๋ฌํ ์ ์๋ค๋ฉด, ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ else: print(distance)
Java
import java.util.*; public class Main { public static final int INF = (int) 1e9; // ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์ // ๋ ธ๋์ ๊ฐ์(N), ๊ฐ์ ์ ๊ฐ์(M), ๊ฑฐ์ณ ๊ฐ ๋ ธ๋(X), ์ต์ข ๋ชฉ์ ์ง ๋ ธ๋(K) public static int n, m, x, k; // 2์ฐจ์ ๋ฐฐ์ด(๊ทธ๋ํ ํํ)๋ฅผ ๋ง๋ค๊ธฐ public static int[][] graph = new int[101][101]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); // ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ for (int i = 0; i < 101; i++) { Arrays.fill(graph[i], INF); } // ์๊ธฐ ์์ ์์ ์๊ธฐ ์์ ์ผ๋ก ๊ฐ๋ ๋น์ฉ์ 0์ผ๋ก ์ด๊ธฐํ for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { if (a == b) graph[a][b] = 0; } } // ๊ฐ ๊ฐ์ ์ ๋ํ ์ ๋ณด๋ฅผ ์ ๋ ฅ ๋ฐ์, ๊ทธ ๊ฐ์ผ๋ก ์ด๊ธฐํ for (int i = 0; i < m; i++) { // A์ B๊ฐ ์๋ก์๊ฒ ๊ฐ๋ ๋น์ฉ์ 1์ด๋ผ๊ณ ์ค์ int a = sc.nextInt(); int b = sc.nextInt(); graph[a][b] = 1; graph[b][a] = 1; } x = sc.nextInt(); k = sc.nextInt(); // ์ ํ์์ ๋ฐ๋ผ ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ ์ํ for (int k = 1; k <= n; k++) { for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]); } } } // ์ํ๋ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅ int distance = graph[1][k] + graph[k][x]; // ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, -1์ ์ถ๋ ฅ if (distance >= INF) { System.out.println(-1); } // ๋๋ฌํ ์ ์๋ค๋ฉด, ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ else { System.out.println(distance); } } }