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

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

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

풀이

sorted(reverse=True)를 이용하여 내림차순을 구현한 뒤 BFS알고리즘을 구현해주시면 됩니다.

코드

# 24445번 알고리즘 수업
from collections import deque
import sys

# 정점의 개수: N 간선의 수: M 시작정점: R
N, M, R = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    d1, d2 = map(int, sys.stdin.readline().split())
    graph[d1].append(d2)
    graph[d2].append(d1)

visited = [False for _ in range(N+1)]    
queue = deque([])
ans = [0 for _ in range(N+1)]

def bfs():
    queue.append(R)
    visited[R] = True
    cnt = 1
    ans[R] = cnt
    while queue:
        s = queue.popleft()
        for i in sorted(graph[s], reverse = True):
            if visited[i] == False:
                queue.append(i)
                visited[i] = True
                cnt += 1
                ans[i] = cnt

bfs()                
for i in range(1,N+1):
    print(ans[i])

출력결과