숨바꼭질(다익스트라)

bfs로도 풀수있는 문제지만 다익스트라의 연습을 위해 다익스트라를 사용하였다.사용알고리즘은 대부분 올바르게 구현하는 편인데 graph의 설정이라던지 구현에서는 다른 사소한 문제들에서 실수가 있는 편인것 같다. 해당부분은 graph를 n^2으로 구현해서 메모리초과가 처음에 났었고, 출력부분에서 distance를 mx로 처리하지않고 mx_idx를 설정해놓는등 실수가 있었다. (그런데 테스트케이스는 맞았다..) 프로그램 구현이라는게 원래 버그를 찾기 힘든 것이기도 하고 사소한 구현에서 실수가 나오기 쉽지만 이런 오류들을 빨리 잡을 수 있거나, 구현하기 전에 미리미리 생각을 다해보고 구현하려는 습관이 필요할 것 같다.

 

또한 사용알고리즘의 시간복잡도를 보다 정확히 알고 있어야겠다.

 

import heapq

import sys

 

input = sys.stdin.readline

 

n, m = map(int, input().split())

INF = int(1e9)

 

distance = [INF]* (n+1)

graph = [[]* (n+2) for _ in range(n+2)]

 

for i in range(m):

    a, b = map(int,input().split())

    graph[a].append(b)

    graph[b].append(a)

 

q = []

distance[1] = 0

heapq.heappush(q,(0,1,0))

#d, start, total

 

while q:

    cd, cx, ct = heapq.heappop(q)

    

    if cx!=1 and distance[cx]<cd:

        continue

 

    for i in range((len(graph[cx]))):

        # print("graph",graph[cx][i])

        cost = 1+ cd

        if cost<distance[graph[cx][i]]:

            heapq.heappush(q,(cost,graph[cx][i],ct+1))

            distance[graph[cx][i]] = cost

 

# for i in range(n):

#     print(distance[i])

 

mx = 0

for i in range(n+1):

    if distance[i]!=INF and mx<distance[i]:

        mx = distance[i]

ct = 0

mx_idx = 0

for i in range(n+1):

    if mx == distance[i]:

        mx_idx =i

        break

for i in range(n+1):

    if mx ==distance[i]:

        ct+=1

print(mx_idx, mx, ct, end=" ")