[백준] 24444번 너비 우선 탐색 1(with python)

윤무무 2023. 2. 8. 13:50

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

1. 내가 작성한 코드

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

n, m, r = map(int, input().split())

graph = [[] for i in range(n+1)]

visit = [0] * (n+1)

cnt = 1

for i in range(m):
  a,b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

def bfs(graph, visit, v):
  global cnt
  queue = deque()
  queue.append(v)
  visit[v] = cnt

  while queue:
    popv = queue.popleft()
    graph[popv].sort()
    for i in graph[popv]:
      if visit[i] == 0:
        queue.append(i)
        cnt+=1
        visit[i] = cnt


bfs(graph, visit, r)

for i in range(1,len(visit)):
  print(visit[i])

 while queue:
    popv = queue.popleft()
    graph[popv].sort()
    for i in graph[popv]:
      if visit[i] == 0:
        queue.append(i)
        cnt+=1
        visit[i] = cnt

자꾸 이 부분의 반복문을 popv로 해주는 걸 까먹네

딥러닝하기~