[PS] BOJ 24445 / 알고리즘 수업 - 너비 우선 탐색 2

Minjun Kim

11 May 2025 • 2 min read

문제 링크: https://www.acmicpc.net/problem/24445

Thumbnail: Photo by Aaron Burden (Unsplash)

그래프를 탐색하는 2가지 기초적인 방법인 DFS와 BFS, 그중 BFS(너비 우선 탐색) 에 대한 문제입니다.

풀이

문제에서도 의사 코드로 주었듯이, BFS(너비 우선 탐색)은 자식 노드보다 형제 노드를 먼저 순회하는 방식입니다. 큐를 활용하면 간단히 구현할 수 있습니다!

문제에서 결과로 출력해야 하는 내용은 각 정점이 몇 번째 순서에 방문되었나 이므로, visited 배열을 bool 타입으로 저장하는 대신 방문 순서를 저장하게끔 구현했습니다.

전체 코드

from sys import stdin

N, M, R = map(int, stdin.readline().split())
visited = [0 for _ in range(N + 1)]             # 방문 여부 리스트. 정점은 1부터 N까지 존재하므로 N+1 크기로 초기화.

graph = [[] for _ in range(N + 1)]                  # 인접 리스트. 정점은 1부터 N까지 존재하므로 N+1 크기로 초기화.
for _ in range(M):
    u, v = map(int, stdin.readline().split())
    graph[u].append(v)                              # u에서 v로 가는 간선 추가
    graph[v].append(u)                              # v에서 u로 가는 간선 추가 (무향 그래프이므로 양방향)

for edges in graph:
    edges.sort(reverse=True)                        # 인접 리스트를 내림차순으로 정렬하여 DFS 순서를 결정한다.

visited[R] = 1                                      # 시작 정점 R을 방문 처리.
queue = [R]                                         # BFS를 위해 방문 예정 정점 큐를 초기화.
order = 2
while queue:
    node = queue.pop(0)                             # 큐에서 정점 하나를 꺼낸다.
    for n in graph[node]:
        if visited[n] == 0:
            visited[n] = order                      # 정점 n을 방문 처리.
            queue.append(n)                         # 정점 n을 큐에 추가.
            order += 1

for i in range(1, N + 1):
    print(visited[i])                               # 방문 순서 출력. visited[i]는 정점 i의 방문 순서.

solution.py