[최단경로] 미래도시

1. 문제 설명

미래도시 쿠팡맨이 N개의 도시들을 돌아다니면서 배달을 하는데, 특정 노드 (K) 를 지나서 노드 (X)에 도착하려고 할 때 몇 개의 도시를 지나가야 하는지를 묻는 문제이다. 각 도시와 도시가 연결된 간선의 비용은 1로 동일하다.

- 전형적인 플로이드 워셜 알고리즘의 문제이다.
- 플로이드 알고리즘의 경우 대칭행렬이 아니기 때문에 그냥 계산해도 양방향을 고려한 그래프가 된다.

2. 코드

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

for a in range(n+1):
    for b in range(n+1):
        if a==b:
            graph[a][b]=0

for _ in range(m):
    a, b = map(int, input().split())
    # 양방향이기 때문에 해당 부분 생각 못함
    graph[a][b] = 1
    graph[b][a] = 1
    
x, k = map(int, input().split())
    
for k in range(n+1):
    for a in range(n+1):
        for b in range(n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])
            

distance = graph[1][k] + graph[k][x]
if distance >= INF:
    print(-1)
else:
    print(distance)

"""
5 7 (n, m)
1 2 (a, b)
1 3
1 4
2 4
3 4
3 5
4 5
4 5 (x, k)
>> 3
"""

3. 코멘트

- 문제를 제대로 이해하는 것도 중요하다. 다 구하고 변수를 잘못 넣어서 계산하는 오류를 범해서 한참 돌아갔었다.