[PART2] 9-1(최단경로): 미래 도시

코뉴·2021년 2월 12일

이코테 최단경로

이코테: 문제풀이

목록 보기

27/28

💥이코테 실전문제 뽀개기💥

💻 9-1 미래 도시

난이도🖤🖤🤍 | 풀이시간 40분 | 제한시간 1초 | 메모리제한 128MB | 기출 M기업 코딩 테스트

📌2021/02/12 작성 코드

# 미래 도시
# 1번 회사에서 출발하여 K번 회사를 방문한 뒤 X번 회사로 가는 데 걸리는 최소 시간
import heapq
import sys

# 전체 회사의 개수 N, 경로의 개수 M
input = sys.stdin.readline
n, m = map(int, input().split())
# 그래프 입력
graph = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1
# x와 k 입력
x, k = map(int, input().split())
# 최단거리 테이블을 무한으로 초기화
INF = int(1e9)
distance = [INF]*(n+1)
# 1번 회사에서 K번 회사를 거쳐 X번 회사로 가는 최소 이동 출력 시간
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) #(거리, 노드)
    distance[start] = 0
    while q:
        # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 거리가 이미 처리된 적이 있다면 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 인접 노드 확인
        for i in range(1, n+1):
            if graph[now][i] == 1:
                cost = dist + 1
                # 현재 노드를 거쳐, 다른 노드로 이동하는 거리가 더 짧은 경우
                if cost < distance[i]:
                    distance[i] = cost
                    heapq.heappush(q, (cost, i))
# 1 에서부터 k로 가는 최단 경로
dijkstra(1)
one_to_k = distance[k]
# k에서부터 x로 가는 최단 경로
distance = [INF]*(n+1)
dijkstra(k)
k_to_x = distance[x]

# 도달할 수 없는 경우
if one_to_k == INF or k_to_x == INF:
    print(-1)
# 도달할 수 있는 경우
else:
 print(one_to_k + k_to_x)

💭 아이디어

출발점인 1에서 K까지의 최단 경로를 dijkstra로 찾고, K에서 X까지의 최단 경로를 dijkstra로 찾는다.
만약 1~K 혹은 K~X 둘 중 하나의 최단경로가 INF라면 이는 경로가 없는 것을 뜻하므로 -1을 출력한다.
만약 1~K와 K~X의 최단경로가 INF가 아니라면 경로가 있는 것을 뜻하므로 두 최단경로의 합을 출력한다.

🤓 문제 해설

전형적인 플로이드 워셜 알고리즘. 현재 문제에서 N의 범위가 100 이하로 매우 한정적이다. 따라서 플로이드 워셜 알고리즘을 이용해도 빠르게 풀 수 있기 때문에, 구현이 간단한 플로이드 워셜 알고리즘을 이용하는 게 유리하다.

이 문제의 핵심 아이디어는 1번 노드에서 X를 거쳐 K로 가는 최단 거리는 (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 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 >= 1e9:
    print("-1")
# 도달할 수 있다면, 최단 거리를 출력
else:
    print(distance)