24445 - 파이썬 :: 내 인생 이대로 ㅈ될 수 없다

24445 - 파이썬

놀만큼논사람 2022. 7. 11. 16:55

2022. 7. 11. 16:55

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버전이다.

다른사람의 풀이