최단 거리 알고리즘

• 다익스트라 알고리즘
  그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• 플로이드 워셜 알고리즘
  모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
• 벨만 포드 알고리즘

✅ 문제

공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 토앻 연결되어 있다. 연결된 2개의 회사는 양방향으로 이동할 수 있다. 도로가 연결되어 있다면 1만큼의 시간으로 이동할 수 있다. A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표다. 이때 A는 가능한 한 빠르게 이동하고자 한다. A가 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성하시오.

첫째 줄에 전체 회사의 개수 N과 경로의 개수 M
둘째 줄부터 M + 1번째 줄에는 연결된 두 회사의 번호
M + 2번째 줄에는 X와 K
X번 회사에 도달할 수 없다면 -1 출력

입력 예시 1

5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5

출력 예시 1

3

입력 예시 2

4 2
1 3
2 4
3 4

출력 예시

-1

💻 코드

INF = int(1e9)

N, M = map(int, input().split())

graph = [[INF] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

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

for i 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][i] + graph[i][b])

X, K = map(int, input().split())

result = graph[1][K] + graph[K][X]

if result < INF:
    print(result)
else:
    print(-1)

설계

플로이드 워셜 알고리즘을 사용하여 모든 지점에서 다른 모든 지점까지의 최단 시간를 구해 1번 회사에서 K번 회사까지의 최단 시간과 K번 회사에서 X번 회사까지의 최단 시간을 구해 더하여 결과를 구하였다.

📝 정리

플로이드 워셜 알고리즘으로 쉽게 해결할 수 있었다.