[백준][Python] 6118번 숨바꼭질 - 코팩

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

6118번: 숨바꼭질

풀이

인접 리스트를 구현해서 bfs를 실행한 뒤 

for문을 통해서 최대거리를 가진 노드 중 가장 번호가 작은 노드, 최대거리와  동일한 최대 거리를 갖고있는 노드의 개수를 구해줍니다.

 

코드

# 6118번 숨바꼭질
import sys
from collections import deque

def bfs():
    max_length = 0
    ans = 1
    same_length = 0

    queue = deque([1])
    visited = [False] * (n+1)
    visited[1] = 1

    while queue:
        c = queue.popleft()
        for i in graph[c]:
            if visited[i] == False:
                visited[i] = visited[c] + 1
                queue.append(i)

    for i in range(1, n+1):
        if max_length < visited[i]:
            max_length = visited[i]
            ans = i
            same_length = 1

        elif max_length == visited[i]:
            same_length += 1
	# 1번 노드의 visited 값을 1로 주었기에 1을 빼줘야합니다.
    return [ans, max_length-1, same_length]


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

print(*bfs())

 

출력결과