https://www.acmicpc.net/problem/24445
24445번: 알고리즘 수업 - 너비 우선 탐색 2
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양
www.acmicpc.net
내 풀이
import sys
from collections import deque
input = sys.stdin.readline
def solution():
V,E,R = map(int,input().split())
visited = [0] * (V+1)
count=1
graph = [[] for _ in range(V+1)]
for _ in range(E):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
def bfs(v):
nonlocal count
q = deque([R])
visited[R] = 1
while q:
v = q.popleft()
graph[v].sort(reverse=True)
for g in graph[v]:
if visited[g]==0:
count +=1
visited[g] = count
q.append(g)
bfs(R)
for i in visited[1:]:
print(i)
solution()
앞서 풀었던 dfs의 bfs버전이다.
다른사람의 풀이
'취준 > 백준' 카테고리의 다른 글
| 7576 - 파이썬 (0) | 2022.07.14 |
|---|---|
| 2606 - 파이썬 (0) | 2022.07.13 |
| 24479 - 파이썬 (0) | 2022.07.11 |
| 18352 - 파이썬 (0) | 2022.07.07 |
| 2178 - 파이썬 (0) | 2022.07.05 |