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

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

2. 문제 풀이

 BFS 탐색 알고리즘을 적용하는 예제 문제입니다.

 

2023.06.30 - [Algorithm] - [탐색/BFS] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 - Python

[탐색/BFS] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 - Python

 1은 오름차순으로 정렬해서 탐색하는 문제였고, 2는 내림차순으로만 정렬해서 탐색하면 됩니다.

 해당 코드의 해설은 위 링크에서 보실 수 있습니다.

 

 

3. 코드

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

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

# BFS 탐색 (탐색할 그래프, 노드 수, 시작 지점)
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [0]*(N+1) #방문 여부를 확인할 리스트
visited[R] = 1 #시작 노드 방문

queue = deque([R]) #인접 노드를 저장할 Queue

#모든 노드를 탐색할 때까지 반복
cnt = 1
while queue:
    #방문 노드
    node = queue.popleft()
    graph[node].sort(reverse=True)  # 내림차순으로 방문

    #방문한 노드의 주변 노드를 큐에 삽입
    for i in graph[node]:
        #방문하지 않는 주변 노드일 경우
        if not visited[i]:
            queue.append(i) #큐에 추가
            cnt += 1
            visited[i] = cnt #방문

#출력
for i in visited[1:]:
    print(i)