미래 도시

1. 문제 설명

출처 : 이코테2021

---

2. 문제 조건

---

3. 문제 해결 아이디어

• 전형적인 최단 거리 문제이므로 최단 거리 알고리즘을 이용해 해결한다.
• N의 크기가 최대 100이므로 플로이드 워셜 알고리즘을 이용해도 효율적으로 해결할 수 있다.
• 플로이드 워셜 알고리즘을 수행한 뒤에 (1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리)를 계산하여 출력한다.

---

4. 답안 예시

INF = int(1e9) #무한을 의미

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

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, 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)