[Shortest Path] 이코테 “미래 도시” Python 풀이

문제

• 방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다.
• 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다.
• 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다.
• 공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다.
• 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다.
• 공중 미래 도시에서의 도로는 마하의 속도로 사람을 이동시켜주기 때문에 특정 회사와 다른 회사가 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다.
• 또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다.
• 소개팅의 상대는 K번 회사에 존재한다.
• 방문 판매원 A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정이다.
• 따라서, 방문 판매원 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표다.
• 이때 방문 판매원 A는 가능한 한 빠르게 이동하고자 한다.
• 방문 판매원이 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성하시오.
• 이때 소개팅의 상대방과 커피를 마시는 시간 등은 고려하지 않는다고 가정한다.
• 예를 들어, N=5, X=4, K=5 이고 회사 간 도로가 7개면서 각 도로가 다음과 같이 연결되어 있을 때를 가정할 수 있다.
  • (1번, 2번), (1번, 3번), (1번, 4번), (2번, 4번), (3번, 4번), (3번, 5번), (4번, 5번)
• 이때 방문 판매원 A가 최종적으로 4번 회사에 가는 경로를 (1번 - 3번 - 5번 - 4번)으로 설정하면, 소개팅에도 참석할 수 있으면서 총 3만큼의 시간으로 이동할 수 있다.
• 따라서 이 경우 최소 이동 시간은 3이다.

입력 조건

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

출력 조건

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

입력 예시

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

4 2
1 3
2 4
3 4

출력 예시

3

-1

풀이

• 플로이드 워셜 알고리즘으로 해결할 수 있으며,
• 1번 노드에서 X를 거쳐 K로 가는 최단 거리는,
• “1번 노드에서 X까지의 최단 거리” + “X에서 K까지의 최단 거리”로 구할 수 있습니다.

예제 코드

import sys

# N, M 입력
n, m = map(int, sys.stdin.readline().rstrip().split())

# 그래프 초기화
graph = [[int(1e9)] * (n+1) for _ in range(n+1)]

# 그래프 대각선 초기화
for i in range(1, n+1):
    graph[i][i] = 0

# 양방향 간선 추가
for _ in range(m):
    start, end = map(int, sys.stdin.readline().rstrip().split())
    graph[start][end] = 1
    graph[end][start] = 1

# X, K 입력
x, k = map(int, sys.stdin.readline().rstrip().split())

# 플로이드 워셜 알고리즘 실행
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])

# [1번 노드에서 K 노드로 가는 최소 비용 + K 노드에서 X 노드로 가는 최소 비용] 출력

# 도달할 수 있을 경우
if (graph[1][k] + graph[k][x] < int(1e9)):
    print(graph[1][k] + graph[k][x])
# 도달할 수 없을 경우
else:
    print(-1)

참고

• 이것이 취업을 위한 코딩 테스트다. with python