알고리즘_코딩테스트/이것이 코딩테스트다
[최단경로] 미래도시
논곰
2021. 12. 7. 23:41
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. 코멘트
- 문제를 제대로 이해하는 것도 중요하다. 다 구하고 변수를 잘못 넣어서 계산하는 오류를 범해서 한참 돌아갔었다.