[BOJ/python] 6118: 숨바꼭질

문제

✔️ silver 1
그래프 이론
그래프 탐색
너비 우선 탐색

문제 흐름

최단거리를 구하는 다른 문제들과는 달리 최장거리를 구해야하는 문제다.
BFS 알고리즘을 사용해 노드를 탐색했다.

큐에 노드넘버와 거리를 함께 삽입해 계산했다.
거리가 max_value보다 크다면 최장거리가 갱신되어 barns 리스트를 현재 탐색한 노드 nx만 포함하는 리스트로 변경한다.
거리가 max_value와 같다면 barns 리스트에 현재 탐색 노드 nx를 추가한다.

탐색이 한번만 이루어지고, n의 크기도 감당할 수 있을 정도라고 생각되어 최장거리 노드들의 최소 노드넘버는 min()을 이용했다.

코드

# 숨바꼭질
# graph

import sys
from collections import deque
input = sys.stdin.readline

def bfs(g: list):
    s = 1
    q = deque([(s, 0)])
    vst = [0 for i in range(n+1)]
    vst[s] = 1

    max_value = 0
    barns = []
    
    while q:
        x, d = q.popleft()
        nd = d + 1
        for nx in g[x]:
            if vst[nx]:
                continue
            q.append((nx, nd))
            vst[nx] = 1
            if nd > max_value:
                barns = [nx]
                max_value = nd
            elif nd == max_value:
                barns.append(nx)
        # print(f"status of barns now: {barns}")
    return (barns, max_value)


if __name__ == "__main__":
    n, m = map(int, input().split())
    g = [ [] for i in range(n+1)]
    for i in range(m):
        a,b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    
    barns, max_value = bfs(g)
    print(min(barns), max_value, len(barns))

마무리

오랜만의 BFS 문제였다.
이제 문제집에 골드 문제만 남았는데 많이 안남았으니 힘내서 풀어봐야겠다.