[백준] 6118(파이썬) - 숨바꼭질

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

6118번: 숨바꼭질

• 이 문제를 읽고 처음 든 생각은 BFS로 풀어야지 였다.
• 이 문제가 생각보다 간단했던 이유는 1번 노드부터 시작한다는 문제의 조건 때문이었다.
• 2차원 graph 배열을 만들어줘서 노드끼리의 관계를 나타내는 지표로 사용하고 visited_cnt를 만들어서 1번에서 각 노드에 갈 때까지의 거리를 기록해줬다.
• 기록해준 vistied_cnt 테이블 값을 갱신하면서 답을 구했고 문제에서 요구하는 최댓값에 관한 정보를 출력해주기 위해 max_num에 visited_cnt에서 가장 큰 값을 담아줘서 출력해줬다.

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

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)
visited_cnt = [0]*(n+1)
# 1번 헛간까지의 거리만 계산해주면 된다
def bfs(node):
    q = deque()
    q.append(node)
    visited_cnt[node] = 1
    while q:
        node = q.popleft()
        for i in graph[node]:
            if visited_cnt[i] == 0:
                visited_cnt[i] = visited_cnt[node] + 1
                q.append(i)
            # print(visited_cnt)

 
bfs(1)
max_num = max(visited_cnt)

print(visited_cnt.index(max_num),max_num-1,visited_cnt.count(max_num))