[Shortest Path] 이코테 “숨바꼭질” Python 풀이

문제

• 동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다.
• 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다.
• 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다.
• 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다.
• 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다.
• 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다.
• 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요.

입력 조건

• 첫째 줄에는 N과 M이 주어지며, 공백으로 구분합니다. (2 <= N <= 20,000), (1 <= M <= 50,000)
• 이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어집니다. (1 <= A, B <= N)

출력 조건

• 첫 번째는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러 개면 가장 작은 헛간 번호를 출력합니다.),
• 두 번째는 그 헛간까지의 거리를,
• 세 번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야 합니다.

입력 예시

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

출력 예시

4 2 3

풀이

• 해당 문제에서 각 노드간의 거리는 1이기 때문에 BFS를 이용하여 최단 거리를 계산할 수도 있지만,
• 해당 포스팅에서는 다익스트라를 사용해 해결했습니다.
• 세부적인 알고리즘은 예제 코드와 같습니다.

예제 코드

import sys
import heapq

# 헛간의 개수 n과 양방향 통로의 개수 m
n, m = map(int, sys.stdin.readline().split())

# 헛간 통로 정보 초기화
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    # 양방향 통로 추가
    graph[a].append((b, 1))
    graph[b].append((a, 1))

# 1차원 최단 거리 배열 초기화
shortest_path = [int(1e9)] * (n+1)

# 우선순위 큐 초기화 (비용, 도착지)
hq = []
heapq.heappush(hq, (0, 1))

# 시작점의 최단 거리 초기화
shortest_path[1] = 0

# 다익스트라 탐색
while hq:

    # 가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기
    now_cost, now = heapq.heappop(hq)

    # 새로 추출한 현재 노드까지의 최단 거리보다 
    # 기존의 현재 노드까지의 최단 거리가 짧을 경우 무시
    if (now_cost > shortest_path[now]):
        continue

    # 현재 노드와 연결된 다른 인접한 노드들을 확인
    for next, next_cost in graph[now]:
        # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
        if (shortest_path[next] > now_cost + next_cost):
            shortest_path[next] = now_cost + next_cost
            heapq.heappush(hq, (shortest_path[next], next))

# 가장 최단 거리가 먼 노드 번호(동빈이가 숨을 헛간의 번호)
result = -1

# 도달할 수 있는 노드 중에서, 가장 최단 거리가 먼 노드와의 최단 거리
max = -int(1e9)

# 가장 최단 거리가 먼 노드와 동일한 최단 거리를 가지는 노드의 개수
count = 0

for i in range(1, n+1):
    if (max < shortest_path[i]):
        result = i
        max = shortest_path[i]
        count = 0
    if (max == shortest_path[i]):
        count += 1

print(result, max, count)

참고

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