[이코테] 최단 경로 알고리즘 - 미래도시

실전 문제

INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

#노드의 개수와 간선의 개수 입력받기.
node,line = map(int,input().split())
#2차원 그래프 무한으로 채워서 선언.
graph = [[INF]*(node+1) for _ in range(node+1)]

#자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1,node+1):
  for b in range(1,node+1):
    if a == b:
      graph[a][b] = 0

#각 간선에 대항ㄴ 정보를 입력받아, 그 값으로 초기화.
for _ in range(line):
  #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,node+1):
  for a in range(1,node+1):
    for b in range(1,node+1):
      graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])
#수행된 결과를 출력
distance = graph[1][k] + graph[k][x]

#도달할 수 없는경우 -1 출력
if distance >= INF:
  print('INF',end=' ')
#도달할 수 있으면 거리 출력
else: 
  print(distance)

결과

---

느낀 점

이 문제는 전형적인 플로이드 워셜 알고리즘 문제다. 문제에서 node값의 범위가 100 이하로 매우 짧기 때문에 플로이드 워셜 알고리즘을 이용해도 빠르게 풀 수 있다. 이 문제의 핵심 아이디어는 1번 노드에서 X를 거쳐 K로 가는 최단 거리가 1번 노드에서 X까지의 최단 거리 +X에서 K까지의 최단거리라는 점이다. 최단 거리 문제는 그림으로 먼저 그려보는 것도 좋은 방법이어서 나는 그림으로 일단 그려보고 문제를 어떻게 풀어나가야 할지 생각해 보았다.