<aside> 🔥 이코테 40번 문제

</aside>

<aside> 🔥 문제 정리

숨바꼭질 하는데 헛간에 숨어야한다. 가장 멀리 떨어져 있는 헛간에 숨으려고한다.

첫째줄 : n : 1 ~ n까지 헛간의 개수, m : 총 m개의 양방향 통로

이후 m개의 줄 : 헛간과 헛간의 통로가 주어진다.

출력 : 가장멀리 떨어져있는 헛간의 번호, 헛간의 깊이, 헛간의 깊이가 같은 헛간의 개수 출력

# 입력값
6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

# 출력값
4 2 3

</aside>

<aside> 🔥 접근 방법

다익스트라 최단거리 방법으로 1번째부터 n번쨰까지 거리를 1씩만 증가시키면서 거리 테이블을 작성.

위 방법대로만 하면 거리 테이블에서 출력값을 얻을 수 있을 것 같다.

</aside>

<aside> 🔥 코드 진행

기본적인 다익스트라에서 누적값에 거리가 따로 없으니 +1을 해준다.

def dijkstra(graph):
    dist = [INF] * m

    q = []
    heapq.heappush(q, (0, 1))
    dist[1] = 0
    while q :
        acc, cur = heapq.heappop(q)
        if dist[cur] < acc :
            continue

        for adj in graph[cur]:
            cost = acc + 1
            if cost < dist[adj] :
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))

    max_dist = max(dist[1:])
    cnt = sum([1 for idx in range(1, m) if dist[idx] == max_dist])
    return dist.index(max_dist), max_dist, cnt

</aside>