백준[24479] - 알고리즘 수업 (너비 우선 탐색 2)

 

 

문제

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

 

 

 

작성한 코드

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

N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [0] * (N+1)
order = 1

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(N+1):
    graph[i].sort(reverse = True)

def bfs(v):
    global order
    q = deque([v])
    visited[v] = order

    while q:
        e = q.popleft()
        for i in graph[e]:
            if visited[i] == 0:
                order += 1
                q.append(i)
                visited[i] = order
    
bfs(R)

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

→ 이전 문제와 풀이 방식은 동일하나, 오름차순으로 방문하냐 vs 내림차순으로 방문하냐 의 차이이다.

→ 해당 문제는 내림차순으로 방문하기 때문에 : sort(reverse = True) 해주면 된다.

 

cf.) 이전 풀이 방식 참고

백준[24444] - 알고리즘 수업 (너비 우선 탐색 1)