[백준] 24445 파이썬(python) : 알고리즘 수업 - 너비 우선 탐색 2

알고리즘 수업 - 너비 우선 탐색 2

 

 

import sys
from collections import deque
n, m, r = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1) ]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visit = [0] * (n + 1)
count = 1
visit[r] = count

def bfs():
    global count
    q = deque()
    q.append(r)
    while q:
        now = q.popleft()
        for i in sorted(graph[now], reverse=True): #1
            if visit[i] == 0:
                count += 1
                visit[i] = count
                q.append(i)
bfs()
for i in range(1, n+1):
    print(visit[i])

 

 

직전문제인 24444번과 비슷한 문제입니다. 

 

 

#1 : 내림차순으로 인접한 노드를 방문하기 위해서 reverse로 정렬