[Python] 백준 6118 - 숨바꼭질

문제 - 숨바꼭질 (Silver1)

[백준 6118] https://www.acmicpc.net/problem/6118

풀이 전략

문제에서 주어진 힌트를 보면, 4, 5, 6 3개의 Node가 거리 2를 가진다고 주어져 있는데, 문제에서 1과의 거리가 멀어지면 멀어질 수록 발냄새가 줄어든다고 주어져 있기 때문에 너비우선탐색(BFS)를 활용하여 가장 깊은 노드를 구할 것이다.

풀이

기존의 BFS Code를 사용하는데, 헛간 번호 & 헛간까지의 거리 & 거리가 같은 헛간의 개수 를 출력하면 된다.

visited 배열로 쓸 수 있는 함수들의 목록을 보면 위의 그림과 같다.
여기서 번호는 index로, 개수는 count로 구할 것이다.

소스 코드

# Question: BJ 6118 (https://www.acmicpc.net/problem/6118)
# Rank : Silver1
# Algorithm : Graph, BFS

import sys
from collections import deque

graph=[[] for _ in range(20001)]
visited=[-1]*20001

def bfs(start):
    q=deque()
    q.append(start)
    visited[start]=0
    while q:
        now=q.popleft()
        for i in graph[now]:
            if visited[i]==-1:
                visited[i]=visited[now]+1 // 방문할때마다 visited를 1씩 늘림
                q.append(i)
                
N,M=map(int,sys.stdin.readline().split())
for _ in range(M):
    a,b=map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
    
bfs(1)

max_dist=max(visited) // visited에서 max = 거리가 제일 긴 Node
max_dist_idx=visited.index(max_dist) // 거리가 제일 긴 Node 번호
max_dist_cnt=visited.count(max_dist) // 제일 긴 거리를 갖는 Node의 개수
print(max_dist_idx,max_dist,max_dist_cnt)

결과