미래 도시(파이썬) / 최단경로 그래프

문제

• 방문원 A는 1에 있는데 K번에 있는 사람과 소개팅을 한다고 한다.
• 그리고 방문원 A는 X 회사로 가야한다.
• 즉, 소개팅을 할 K번 회사를 방문 후에 X 회사에 최종 도착해야 한다.
• 이 때, 총 N개의 도시와 M개의 도로가 주어질 경우 A가 갈 경로의 최단 거리를 구하라

 

입력

• 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다(1<= N, M<=100)
• 둘째 줄부터 M+1 번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.
• M+2번 째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다 (1<= K <= 100)

 

 

출력

• 첫째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.
• 만약 X번 회사에 도달할 수 없다면 -1을 출력한다.

---

풀이

전체 경로를 구해서 1-> K + K -> X 의 경로를 구해주면 된다.

플로이드 와샬 알고리즘을 활용한다(v를 거쳐 a~b 가는 모든 최단경로 갱신)

import sys

sys.stdin = open("input_9-2.txt","r")
sys.stdout = open("output_9-2.txt", "w")

# input
INF = 9999999
n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신 갱신
for i in range(1,n+1):
    graph[i][i] = 0

# input 처리
for _ in range(m):
  src, dst = map(int, input().split())
  graph[src][dst] = 1
  graph[dst][src] = 1

# k 를 거쳐 x로 간다
x , k = map(int, input().split())

print(graph)

# 플로이드-와샬
for v 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][v] + graph[v][b])

# 출력
if graph[1][k] >= INF or graph[k][x] >= INF:
    print(-1)
else:
    print(graph[1][k] + graph[k][x])