[최단경로] 숨바꼭질

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 40분

1. 문제 설명

- 숨바꼭질을 하는데 술래는 1에서 출발한다. 이때 계산 결과 1번에서 다른 노드의 최단거리 중 술래와 가장 먼 거리에 숨으면 가장 괜찮다는 것을 알아넀다. 그래서 숨는 위치, 가장 먼 최단거리, 이와 같은 값을 가지는 노드의 개수를 출력하는 문제

2. 접근 방식

- 다익스트라 알고리즘을 활용한다.

- 단, 단방향이 아닌 양방향이기 때문에 input을 받을 때 그래프를 양방향에서 받는 느낌으로 넣어줘야 한다. a, b가 (input)으로 들어온다면, graph[a].append(b), graph[b].append(a) 둘 다 넣어줘야 한다.

3. 코드

import heapq
n, m = map(int, input().split())
INF = 1e9
graph = [[] for i in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dijkstra(start):
    distance = [INF] *(n+1)
    q = [(0, start)]
    distance[start] = 0
    while q:
        dist, node = heapq.heappop(q)
        if distance[node] < dist:
            continue
        for next_node in graph[node]:
            cost = dist + 1
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q, (distance[next_node], next_node))
    return distance
dist = dijkstra(1)

answer = list(map(lambda x: -1 if x == INF else x, dist))
tmp =[]
b = max(answer) # 헛간과의 거리

for i in range(1, n+1):
    if answer[i] == b:
        tmp.append(i)
a = sorted(tmp)[0]
c = len(tmp)
print(a, b, c)

4. 코멘트

- 오랜만에 내 힘으로 온전히 문제를 해결한 거 같아서 내심 뿌듯했다. 물론 알고리즘을 조금 참고하기는 했지만, 그래도 예전보다는 많이 나아진 것 같다.(예전에는 흐름도 이해하기 힘들었기에...)

- 문제를 푸는데 처음에는 양방향 그래프라는 것을 고려 안해서 문제가 있었지만 잘 해결했다는 점에서 스스로 대견하다.