[최단경로] 미래도시

⭐ 성찰

문제를 풀기 전에 항상 시간 복잡도를 먼저 판단해서 해당 알고리즘으로 풀이할 수 있는지를 점검하자.

시간 복잡도 조건을 충족하는 여러 알고리즘 중 가장 구현이 쉬운 방식을 택하는 현명함을 갖추자.

❓ 문제 상황

[미래도시](이코테 p.259)

👨‍💻 문제 해결: 최단경로 알고리즘

✅ 1차 풀이: 다익스트라 알고리즘

1번 건물에서 k번 건물을 거쳐 x번으로 가는 최단 경로를 구해야하므로, 1번에서 k번까지 가는 최단 경로 + k번에서 x번까지 가는 최단경로를 각각 구해 합하면 됨.
시간 복잡도 판단: 다익스트라 알고리즘은 O(ElogV)를 가지므로, 최대 V = 100, E = 100,000으로 시간 내에 풀이 할 수 있음.
1. 연결된 노드 정보를 받아 연결 리스트 형태의 그래프에 (노드, 비용) 형태로 저장함.
2. 1을 시작으로 다익스트라를 돌려 1번 노드에서 출발했을 때 각 노드에 도달하는 최단 경로를 구함.
3. k를 시작으로 다익스트라를 돌려 k번 노드에서 출발했을 때, 각 노드에 도달하는 최단 경로를 구함.
4. 1-> k -> x로의 최단 경로를 계산해 반환함.
```
import sys
from heapq import heappush, heappop
```

input = sys.stdin.readline INF = int(2e9)

n, m = map(int, input().split()) graph = [[] for in range(n+1)] for in range(m): v1, v2 = map(int, input().split()) graph[v1].append((v2, 1)) graph[v2].append((v1, 1)) x, k = map(int, input().split()) d1 = [INF] (n+1) d2 = [INF] (n+1)

def dijkstra(s, d): q = [] heappush(q, (0, s)) d[s] = 0 while q: cost, cv = heappop(q) if d[cv] < cost: continue for info in graph[cv]: v, edge = info nc = cost + edge if nc < d[v]: d[v] = nc heappush(q, (nc, v))

dijkstra(1, d1) dijkstra(k, d2) distance = d1[k] + d2[k] print(distance if distance < INF else '-1')


### ✅ 2차 풀이: 플루이드 워셜 알고리즘
- 1번 건물에서 k번 건물을 거쳐 x번으로 가는 최단 경로를 구해야하므로, 1번에서 k번까지 가는 최단 경로 + k번에서 x번까지 가는 최단경로를 각각 구해 합하면 됨.
- 시간 복잡도 판단: 플루이드 워셜 알고리즘은 O(n^3)이지만 최악의 경우에도 n = 100이므로 시간 내에 풀이 가능.
```python
import sys

input = sys.stdin.readline
INF = int(2e9)

n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]

for x in range(1, n+1):
  for y in range(1, n+1):
    if x == y:
      graph[x][y] = 0

for _ in range(m):
  x, y = map(int, input().split())
  graph[x][y] = 1
  graph[y][x] = 1

end, visit = map(int, input().split())

for k in range(1, n+1):
  for x in range(1, n+1):
    for y in range(1, n+1):
      graph[x][y] = min(graph[x][y], graph[x][k] + graph[k][y])

for i in range(1, n+1):
  print(graph[i])

result = graph[1][visit] + graph[visit][end]
print(result if result < INF else -1)

ericagong / algorithm_solving