BOJ 6118 - 숨바꼭질

문제

백준 온라인 저지 - 6118번

풀이 과정

시작 정점에서 다른 모든 정점까지의 거리 중 가장 긴 경로를 찾는 문제입니다.

다익스트라 알고리즘 을 활용하여 한 정점으로부터 다른 모든 정점까지의 최단 거리를 구한 다음,
가장 거리가 먼 정점을 찾아주면 됩니다.

이때 구현의 편의를 위해서 dist 배열을 거리값과 정점 번호순으로 정렬하여 답을 구했습니다.

코드

import sys
import heapq


INF = sys.maxsize
N, M = list(map(int, sys.stdin.readline().split()))
adj = [[] for _ in range(N+1)]
for _ in range(M):
    frm, to = list(map(int, sys.stdin.readline().split()))
    adj[frm].append(to)
    adj[to].append(frm)


def dijkstra():
    pq = []
    dist = [INF for _ in range(N+1)]

    dist[1] = 0
    heapq.heappush(pq, (0, 1))

    while pq:
        cost, here = heapq.heappop(pq)

        if dist[here] < cost:
            continue

        for there in adj[here]:
            next = cost + 1  # 각 정점 사이의 가중치는 1이다.
            if next < dist[there]:
                dist[there] = next
                heapq.heappush(pq, (next, there))

    # 헛간 가장 먼 것을 찾는다.
    temp = list(zip(dist[1:], range(1, len(dist))))
    temp = sorted(temp, key=lambda x: (-x[0], x[1]))

    # 거리가 같은 헛간 개수를 찾는다.
    same = 1
    for d, _ in temp[1:]:
        if d == temp[0][0]:
            same += 1

    return [temp[0][1], temp[0][0], same]


def solution():
    ans = dijkstra()
    return ' '.join(map(str, ans))


print(solution())