[백준 6118번] 숨바꼭질

import sys
from collections import deque

input = sys.stdin.readline

# 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다
# 모든 헛간은 M(1<= M <= 50,000)개의 양방향 길로 이어져 있고, 그 양 끝을 A_i 와 B_i(1<= A_i <= N; 1 <= B_i <= N; A_i != B_i)
# 또한 어떤 헛간에서 다른 헛간으로는 언제나 도달 가능하다고 생각해도 좋다. 

# 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다

# 출력 : 숨어야 하는 헛간 번호(만약 거리가 같은 헛간이 여러개면 가장 작은 헛간 번호를 출력), 헛간까지의 거리, 헛간과 같은 거리를 갖는 헛간의 개수

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

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

visited = [False]*(n+1)

answer = []

maximum = -1

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

def bfs():

    global maximum
    global answer

    q = deque([(1,0)])
    visited[1] = True

    while q:

        v, depth = q.popleft()

        if depth > maximum:
            answer = [v]
            maximum = depth
        elif depth == maximum:
            answer.append(v)
        
        for n in graph[v]:
            if not visited[n]:
                q.append((n,depth+1))
                visited[n] = True

bfs()

print(f"{min(answer)} {maximum} {len(answer)}")

 

본 문제는 N개의 노드와 M개의 간선이 주어졌을 때, 1번 노드에서부터 '가장 멀리 떨어져 있는 노드 번호의 최솟값' /  '떨어진 거리' / '가장 멀리 떨어져 있는 노드의 개수'를 구하는 문제이다.

 

문제를 보자마자 그래프 문제라는 것을 인지하였고, 최단 경로로 탐색하면서 특정 노드로부터의 거리를 저장해야하기 때문에 BFS 알고리즘을 사용하였다.

 

최대 깊이(maximum) 변수를 선언한 뒤 현재 노드까지의 거리가 해당 변수보다 더 클 경우에 최대 거리를 갱신해주었고, 거리가 같은 경우에는 노드 목록(answer)에 추가해주는 방식으로 해결하였다.

 

BFS를 복습해볼 수 있었던 간단한 문제였다 :)