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

 

[ Contents ]

 

 

1. 문제 (링크 참조)

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

 

 

2. 문제 풀이

 너비 우선 탐색(BFS)을 사용하는 기본 예제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 

 

 

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()  # 오름차순으로 방문

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

 오름차순으로 방문하므로, 차후에 방문할 주변 노드를 탐색하기 전에 정렬부터 합니다.

 방문할 때마다 cnt를 올려가며 몇 번째로 방문했는지를 표시합니다.

 

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

 이후 방문순서를 출력합니다.

 

 

<전체 코드>

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()  # 오름차순으로 방문

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

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