C++ 코딩테스트 강좌, 너비 우선 탐색

여러분 안녕하세요! 오늘은 코딩테스트에 자주 등장하는 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘에 대해 설명하겠습니다. 이 강좌에서는 BFS의 기본 개념을 살펴보고, 이를 활용한 알고리즘 문제를 하나 풀어 보도록 하겠습니다.

BFS란 무엇인가?

너비 우선 탐색(BFS)은 그래프 이론에서 노드를 탐색하는 알고리즘 중 하나입니다. BFS는 한 노드에서 시작하여 인접한 모든 노드를 탐색한 후, 그 다음 단계에서 인접한 노드를 탐색하는 방식으로 진행됩니다. 이를 통해 최단 경로 문제를 풀거나, 최단 거리도 계산할 수 있습니다.

BFS의 특징

  • 큐(Queue) 자료구조 사용: BFS는 탐색할 노드를 저장하기 위해 큐 자료구조를 사용합니다.
  • 최단 경로 보장: BFS를 사용하면 가중치가 동일한 그래프의 경우 최단 경로를 보장합니다.
  • 레벨 순으로 탐색: BFS는 각 레벨을 순차적으로 탐색하기 때문에, 가까운 노드부터 먼 노드로 탐색이 이루어집니다.

문제 설명

이제 BFS를 활용한 간단한 문제를 살펴보겠습니다.

문제: 01-너비 우선 탐색을 통한 최단 거리 계산

주어진 무방향 그래프에서 특정 시작 노드로부터 모든 다른 노드까지의 최단 거리를 계산하는 프로그램을 작성하시오. 입력은 그래프의 노드 수와 간선 수, 그리고 각 간선의 양쪽 노드를 나타냅니다.

입력 형식

첫 번째 줄에는 그래프의 노드 수 N (1 ≤ N ≤ 10^5)와 간선 수 M (1 ≤ M ≤ 2 * 10^5)이 주어진다.
다음 M줄에 걸쳐 각 간선의 양쪽 노드 u, v (1 ≤ u, v ≤ N)를 나타낸다.
마지막 줄에는 시작 노드 S가 주어진다.

출력 형식

각 노드까지의 최단 거리를 공백으로 구분하여 출력한다.
연결되어 있지 않은 노드는 -1로 출력한다.

문제 해결 과정

BFS를 사용하여 문제를 해결하기 위한 과정을 단계별로 살펴보겠습니다.

1단계: 그래프 표현

그래프를 표현하기 위해 인접 리스트를 사용하겠습니다. 인접 리스트는 각 노드에 연결된 다른 노드들을 리스트 형태로 저장합니다. 이를 통해 메모리를 효율적으로 사용할 수 있습니다.

2단계: BFS 구현

BFS는 큐를 사용하여 인접한 노드를 탐색합니다. 탐색 순서는 다음과 같습니다:

  1. 시작 노드를 큐에 삽입하고, 거리를 0으로 초기화합니다.
  2. 큐에서 노드를 하나 꺼내고, 그 노드에 인접한 모든 노드를 확인합니다.
  3. 탐색한 노드가 방문하지 않은 노드라면, 거리를 현재 노드의 거리 + 1로 설정하고 큐에 삽입합니다.
  4. 큐가 비어있을 때까지 이 과정을 반복합니다.

3단계: 코드 작성

이제 위의 과정을 바탕으로 C++ 코드를 작성해 보겠습니다.


#include 
#include 
#include 
#include 

using namespace std;

const int MAX_N = 100000;
vector graph[MAX_N + 1];
int dist[MAX_N + 1];

void bfs(int start, int n) {
    queue q;
    fill(dist, dist + n + 1, -1);  // 거리 초기화
    dist[start] = 0;                // 시작 노드 거리 설정
    q.push(start);                   // 큐에 시작 노드 삽입

    while(!q.empty()) {
        int current = q.front();
        q.pop();
        
        for(int neighbor : graph[current]) {
            if(dist[neighbor] == -1) { // 방문하지 않은 노드
                dist[neighbor] = dist[current] + 1;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int N, M, S;
    cin >> N >> M;
    
    for(int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);         // 무방향 간선 추가
        graph[v].push_back(u);
    }
    cin >> S;

    bfs(S, N); // BFS 호출

    for(int i = 1; i <= N; ++i) {
        cout << dist[i] << " ";       // 거리 출력
    }
    cout << endl;

    return 0;
}

4단계: 코드 실행 및 결과

위의 코드를 실행하면, 시작 노드 S로부터 각 노드까지의 최단 거리를 계산하여 출력합니다. 예를 들어, 아래와 같은 입력이 주어진다면:

입력 예제:

6 7
1 2
1 3
2 4
3 4
4 5
4 6
5 6
1

출력 예제:

0 1 1 2 3 2

5단계: 결론

이번 강좌에서는 C++ 코딩테스트에서 자주 등장하는 너비 우선 탐색(BFS) 알고리즘에 대해 알아보았습니다. BFS는 최단 경로 문제를 해결하는 데 유용하며, 다양한 문제에 적용될 수 있습니다. 이 알고리즘을 잘 이해하고 활용한다면 코딩 테스트에서 좋은 성과를 거둘 수 있을 것입니다.

이번 강좌가 여러분의 취업 준비에 도움이 되었기를 바랍니다. 감사합니다!