[최단 경로] 미래 도시 (실전문제, 이것이 코딩테스트다 with 파이썬)

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

 

 

문제

 

 

해설

• N의 범위가 100 이하로 매우 한정적 → 플로이드 워셜 O(N^3) 알고리즘으로 풀 수 있음
• (1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리) 문제
• 먼저 그림을 그려보는 것도 좋은 방법

풀이

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

# 노드의 개수 및 간선의 개수를 입력받기
n, m = map(int, input().split())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range91, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0
            
# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # 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. 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][k] + graph[k][b])
 
# 수행된 결과를 출력
distance= graph[1][k] + graph[k][x]

# 도달할 수 없는 경우, -1을 출력
if distance >= INF:
    print("-1")
# 도달할 수 있다면, 최단 거리를 출력
else:
    print(distance)

 

해석

변수 : 노드 개수 N, 간선 개수 M, 2차원 최단거리 graph, 거쳐갈 노드 K, 목적지 X

 

1. 노드 개수 N, 간선 개수 M 입력받기

2. 2차원 최단거리 graph 무한으로 초기화

ㄴ 자기 자신 → 자기 자신 경우에는 비용 0으로 초기화

ㄴ 간선 정보 입력받기 & 비용 1로 설정

3. 거쳐갈 노드 K, 목적지 X 입력받기

4. 플로이드 워셜 알고리즘

ㄴ 거쳐갈 노드 n번 반복문

ㅡㅡ 출발 노드 n번 반복문

ㅡㅡㅡㅡ 도착 노드 n번 반복문

5. [1번 노드 ~ K 노드 최단 거리] + [K 노드 ~ X 노드 최단 거리]

6. 정답 출력 : 도달할 없는 경우 -1 or 최단 거리 출력