[Python/파이썬] 백준 6118번 숨바꼭질

https://www.acmicpc.net/problem/6118

 

코드

from collections import deque

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

# BFS
q = deque([1])
dist = [int(1e9)]*(n+1)
dist[1] = 0
ans = [-1, -1, -1]
while q:
    now = q.popleft()
    for nx in graph[now]:
        if dist[nx] > dist[now]+1:
            q.append(nx)
            dist[nx] = dist[now]+1
            if ans[1] < dist[nx]:   # 더 먼 헛간 발견
                ans = [nx, dist[nx], 1]
            elif ans[1] == dist[nx]:    # ans와 같은 거리 헛간 발견
                if ans[0] > nx:
                    ans[0] = nx
                ans[2] += 1
print(*ans)

 

1번 헛간에서부터 BFS를 이용하여 탐색하며 다른 모든 헛간들까지의 거리를 구한다. 이때 ans에 가장 먼 헛간의 번호와 거리, 같은 거리를 가진 헛간의 개수를 리스트로 저장한다. 만약 같은 거리를 가진 헛간이 나온다면 현재 ans의 값과 지금 발견한 헛간 중 번호가 작은 헛간의 번호를 저장한다.