티스토리 뷰

코딩/파이썬 백준

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

박상어 2022. 3. 8. 21:12
728x90

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

 

6118번: 숨바꼭질

재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자.   재

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from collections import deque
 
 
def bfs(v):
    dq = deque()
    dq.append(v)
    visit[v] = True
    tmp, tmp_idx = 0, 0
    while dq:
        v = dq.popleft()
        for i in lst[v]:
            if not visit[i]:
                chk[i] = chk[v] + 1
                visit[i] = True
                dq.append(i)
            if tmp < chk[i]:
                tmp_idx = i
                tmp = chk[i]
            elif tmp == chk[i]:
                tmp_idx = min(tmp_idx, i)
    return tmp_idx
 
 
N, M = map(int, input().split())
lst = [[] for _ in range(N + 1)]
visit = [False for _ in range(N + 1)]
chk = [0 for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)
 
for i in lst:
    i.sort()
r_num = bfs(1)
 
l_num, cnt_num = chk[r_num], 0
for i in chk:
    if chk[r_num] == i:
        cnt_num += 1
print(r_num, l_num, cnt_num)
 cs

 

'코딩 > 파이썬 백준' 카테고리의 다른 글

백준 11256 사탕 (파이썬)  (0) 2022.03.10
백준 5648 역원소 정렬 (파이썬)  (0) 2022.03.10
백준 15815 천재 수학자 성필 (파이썬)  (0) 2022.03.08
백준 2583 영역 구하기 (파이썬)  (0) 2022.03.07
백준 2667 단지번호붙이기 (파이썬)  (0) 2022.03.07
댓글