728x90
문제를 정확히 읽읍시다.
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)) #최솟값, 가장 큰값(발냄새 적게 나는 헛간), 거리가 똑같은 지점들
728x90
'백준 풀이' 카테고리의 다른 글
[백준/BOJ] - 9205번 python 풀이 - bfs (0) | 2023.04.05 |
---|---|
[백준/BOJ] - 1240번 python 풀이 - bfs (0) | 2023.04.04 |
[백준/BOJ] - 16174번 python 풀이 - dfs (0) | 2023.04.03 |
[백준/BOJ] - 15900번 python 풀이 - dfs (0) | 2023.04.02 |
[백준/BOJ] - 13265번 python 풀이 - bfs (0) | 2023.03.27 |