[Python][백준/BOJ] 6118번 : 숨바꼭질

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

6118번: 숨바꼭질

 

내 코드

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

n, m = map(int, input().split())
graph =[[] for _ in range(n+1)]
visited =[0 for _ in range(n+1)]
depth = [0]*(n+1)
num = []
cnt =0

for _ in range(m):
    a, b =  map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(x):
    q= deque()
    q.append(x)    
    while q:
        barn = q.popleft()
        for i in graph[barn]:
            if not visited[i]:
                visited[i] =1
                q.append(i)
                depth[i] = depth[barn]+1
bfs(1)
depth[1] =0

for i in range(len(depth)):
    if max(depth) == depth[i]:
        num.append(i)
        cnt+=1
print(num[0], max(depth), cnt)

 

코드 리뷰, BFS

해당 문제는 1부터 시작한다는 점에서 체감 난이도를 대폭 낮춰주는 것 같다.

문제는 이 방식으로 접근했다.

1. 1에 연결된 수의 거리를 계산한다.
2. 각 거리가 저장되어 있는 배열을 가지고, 조건에 따라 출력한다.

 

def bfs(x):
    q= deque()
    q.append(x)    
    while q:
        barn = q.popleft()
        for i in graph[barn]:
            if not visited[i]:
                visited[i] =1
                q.append(i)
                depth[i] = depth[barn]+1

BFS 함수는 위와 같다. 시간 복잡도를 위해 deque을 사용했으며, 1로부터 연결되어 있는 모든 헛간을 방문해서 거리를 계산했다.

거리는 (현재 헛간의 거리 +1)을 통해 뻗어나가도록 했다. 

 

bfs(1)
depth[1] =0
cnt =0
for i in range(len(depth)):
    if max(depth) == depth[i]:
        num.append(i)
        cnt+=1

그리고 1부터 출발하기 때문에 bfs(1)을 해주었다. 이후 depth[1]의 거리는 1 이상이 될 수 있는데, 1의 거리는 필요없으니까 0으로 초기화해주고 카운트한다.

이후 문제에서 요구하는 조건에 따라 결과값을 출력하면 정답이다.