[백준/BOJ] - 6118번 python 풀이 - bfs

---

문제를 정확히 읽읍시다.

 

1. 1번 헛간에서 가장 먼 헛간을 찾아라

2. 1번에서 시작하고 bfs로 돌리면 근처에 있는 노드들을 우선 탐색하기 때문에 depth를 계산하기 용이하다.

3.  idx값을 구해야하므로 enumerate를 활용하면 값을 쉽게 얻을 수 있다.

---

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

n, m = map(int,input().split()) #노드 수, 라인 수
arr = [[] for _ in range(n+1)]
depth = [0 for _ in range(n+1)]
ok = [False] * (n+1)
for _ in range(m):
    a,b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)

def bfs(n):
    ok[n] = True #방문 처리
    q = deque([]) #deque 선언
    q.append(n) #q에 삽입
    while q: #q에 뭔가가 있다면
        v = q.popleft() 
        for i in arr[v]: 
            if not ok[i]: 
                depth[i] = depth[v] + 1 #깊이
                q.append(i) #q에 삽입
                ok[i] = True #방문처리

bfs(1)
temp = [] #
maxi = max(depth) #
for idx,item in enumerate(depth):
    if item == maxi:
        temp.append(idx)

print(min(temp), maxi, len(temp)) #최솟값, 가장 큰값(발냄새 적게 나는 헛간), 거리가 똑같은 지점들