[Python/백준] 24445 알고리즘 수업 - 너비 우선 탐색 2

문제링크

https://www.acmicpc.net/problem/24445

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

---

코드

from collections import deque
input = __import__('sys').stdin.readline
n,m,r = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
visited = [False for _ in range(n+1)]
result = [0 for _ in range(n)]
def bfs(start):
    global result
    num = 1
    visited[start] = True
    q = deque([start])
    while q:
        node = q.popleft()
        result[node-1] = num
        num+=1
        for i in sorted(graph[node], reverse=True):
            if not visited[i]:
                visited[i] = True
                q.append(i)
bfs(r)
print(*result, sep='\n')

---

문제풀이

기본적인 bfs 문제이다. 주의할 점은 인접 정점은 내림차순으로 방문해야 한다.

sorted(graph[node], reverse=True), 인접한 정점들을 내림차순으로 정렬하여 방문한다.