알고리즘||코딩테스트/백준
[백준 24444번] 알고리즘 수업 - 너비 우선 탐색 1
째로스
2023. 6. 26. 17:58
https://www.acmicpc.net/problem/24444
24444번: 알고리즘 수업 - 너비 우선 탐색 1
첫째 줄에 정점의 수 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
n,m,r=map(int,sys.stdin.readline().split())
graph=[[] for _ in range(n+1)]
visited=[0 for _ in range(n+1)]
def bfs(start):
cnt=1
visited[start]=cnt
que=deque([start])
while que:
now=que.popleft()
for i in graph[now]:
if visited[i]==0:
cnt+=1
visited[i]=cnt
que.append(i)
for i in range(m):
a,b=map(int,sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
for i in range(1,n+1):
graph[i].sort()
bfs(r)
for i in range(1,n+1):
print(visited[i])전형적인 BFS를 사용하여 풀수 있는 문제였다.
