[백준_그래프] 알고리즘 수업 - 너비 우선 탐색 1

문제

오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.

너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.

 

bfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    for each v ∈ V - {R}
        visited[v] <- NO;
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    enqueue(Q, R);  # 큐 맨 뒤에 시작 정점 R을 추가한다.
    while (Q ≠ ∅) {
        u <- dequeue(Q);  # 큐 맨 앞쪽의 요소를 삭제한다.
        for each v ∈ E(u)  # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
            if (visited[v] = NO) then {
                visited[v] <- YES;  # 정점 v를 방문 했다고 표시한다.
                enqueue(Q, v);  # 큐 맨 뒤에 정점 v를 추가한다.
            }
    }
}

 

 

 

입력

 

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

 

출력

 

첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

 

 

풀이

 

이 문제는 너비 우선 탐색(BFS)을 사용하여 주어진 무방향 그래프에서 시작 정점 R로부터 각 정점의 방문 순서를 찾는 문제입니다.

 

문제를 해결하기 위한 접근 방식을 다음과 같이 설명할 수 있습니다.

1. 그래프 구성
   - 입력으로 주어지는 정점의 수 N, 간선의 수 M, 시작 정점 R에 대한 정보를 받습니다.
   - 그래프를 구현하기 위해 빈 그래프를 초기화합니다. 이 그래프는 각 정점과 해당 정점과 연결된 인접 정점들을 저장합니다.
   - 방문 여부를 나타내기 위한 visited 리스트를 초기화합니다.
   - 방문 순서를 기록할 변수 c를 1로 초기화합니다.

 

2. 간선 정보 입력
   - M개의 간선 정보를 입력받습니다. 간선 정보는 양방향으로 연결된 두 정점의 쌍과 가중치 1로 주어집니다.
   - 입력 받은 간선 정보를 이용하여 그래프를 구성합니다. 양방향 간선으로 구성하여 양쪽 방향으로 이동할 수 있도록 합니다.

 

3. 그래프 정렬
   - 각 정점의 인접 정점을 오름차순으로 정렬합니다. 이렇게 하면 나중에 BFS를 수행할 때 인접 정점을 오름차순으로 방문할 수 있습니다.

 

4. BFS 함수 구현
   - BFS 함수를 정의합니다. 이 함수는 그래프, 시작 정점, 방문 여부를 나타내는 visited 리스트를 인자로 받습니다.
   - 큐를 사용하여 BFS를 수행합니다. 시작 정점 R을 큐에 추가하고 방문 여부를 표시합니다.
   - 큐가 비어질 때까지 다음 과정을 반복합니다.
     - 큐에서 정점을 하나 꺼내고, 해당 정점과 연결된 인접 정점들을 방문합니다.
     - 방문한 정점을 큐에 추가하고 방문 순서를 증가시킵니다.

 

5. BFS 함수 호출
   - 위에서 구현한 BFS 함수를 시작 정점 R로 호출하여 각 정점의 방문 순서를 계산합니다.

 

6. 결과 출력
   - 방문 순서를 저장한 visited 리스트를 순회하면서 각 정점의 방문 순서를 출력합니다.
   - 시작 정점의 방문 순서는 1로 시작하며, 시작 정점에서 방문할 수 없는 경우 0을 출력합니다.

 

 

이러한 방식으로 주어진 그래프에서 BFS를 수행하여 각 정점의 방문 순서를 구할 수 있습니다.

 

 

 

 

소스 코드

 

import sys
from collections import deque

# 재귀 깊이 제한 설정
sys.setrecursionlimit(10 ** 6)

# 입력을 빠르게 받기 위해 sys.stdin.readline 사용
input = sys.stdin.readline

# 정점의 수 N, 간선의 수 M, 시작 정점 R 입력 받기
n, m, r = map(int, input().split())  # 정점의 수, 간선의 수, 시작 정점

# 그래프 초기화
graph = [[] for _ in range(n+1)]  # 그래프 정보를 저장하는 리스트
visited = [0] * (n+1)  # 방문 순서를 저장하는 리스트. 0이면 방문하지 않은 상태

c = 1  # 방문 순서를 나타내는 변수

# BFS 함수 정의
def bfs(graph, start, visited):
    global c  # 방문 순서를 나타내는 전역 변수 사용
    queue = deque([start])  # 큐를 사용하여 BFS 수행 시작
    visited[start] = c  # 시작 정점을 방문한 것으로 표시
    
    while queue:
        v = queue.popleft()  # 큐의 맨 앞에서 정점 하나를 꺼냄
        for i in graph[v]:  # 현재 정점과 연결된 인접 정점들에 대해 반복
            if visited[i] == 0:  # 방문하지 않은 정점인 경우
                queue.append(i)  # 큐에 추가하여 나중에 방문하도록 함
                c += 1  # 방문 순서 증가
                visited[i] = c  # 방문한 정점의 순서를 저장

# m개의 연결된 간선 정보 입력받기
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # 양방향 간선으로 연결된 노드 정보 추가
    graph[b].append(a)  # 양방향 간선으로 연결된 노드 정보 추가

# 그래프의 인접 노드 정보를 오름차순 정렬
for i in range(n+1):
    graph[i].sort()

# BFS 함수 호출하여 시작 정점 R로부터 각 정점의 방문 순서 계산
bfs(graph, r, visited)

# 결과 출력
for i in range(1, n+1):
    print(visited[i])  # 각 정점의 방문 순서 출력