[99클럽/코딩테스트 챌린지/C++] 너비 우선 탐색(BFS)와 방문 순서 기록을 통한 그래프 탐색

오늘은 너비 우선 탐색(BFS) 을 사용해 그래프의 정점을 탐색하면서 방문 순서를 기록하는 방법을 배웠습니다. BFS는 큐(queue)를 사용하여 가까운 정점부터 방문하므로, 그래프의 각 정점을 최단 거리 순서로 방문할 수 있습니다. 이번 문제에서는 각 정점의 방문 순서를 기록하고, 시작 정점에서 도달할 수 없는 정점은 0으로 표시하도록 했습니다.

문제링크 :

https://www.acmicpc.net/problem/24444

문제 접근 과정

1, 문제 분석과 그래프 구현 방식 선택

• 주어진 그래프는 무방향 그래프로, 각 간선은 양방향으로 연결됩니다. 이를 위해 양방향 간선을 인접 리스트 형태로 구현해야 했습니다.
• 그래프 탐색에서는 인접 행렬보다 인접 리스트가 메모리와 속도 면에서 더 효율적이므로, 인접 리스트를 사용해 그래프를 구현하였습니다.

2, BFS 탐색과 방문 순서 기록

• BFS를 시작점에서 실행하여, 각 정점의 방문 순서를 기록해야 합니다.
• queue를 사용해 현재 정점에서 가까운 인접 정점들을 순서대로 탐색하며 방문 순서를 기록합니다. 이때, 방문 순서를 order라는 증가하는 변수로 관리하여 visited 배열에 저장합니다.

3, 오름차순 방문 조건

• 문제에서 각 정점의 인접 정점들은 오름차순으로 방문해야 하므로, 모든 인접 리스트를 오름차순으로 정렬했습니다.
• 인접 정점을 오름차순으로 방문함으로써 문제에서 요구한 순서대로 탐색이 이루어집니다.

코드 풀이

아래는 문제 해결을 위한 최종 코드입니다:

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<vector<int>> map;
int visited[100005];
int N, M, R;
int order = 1;
void bfs(int start)
{
    queue<int> q;
    q.push(start);
    // 현재 방문한 정점에서 order 값을 증가 시켜서 저장한다.
    visited[start] = order++;
    while (!q.empty())
    {
        int current = q.front();//현재 방문할 정점을 반환한다.
        q.pop();

        for (auto next : map[current])// 인접한 정점들을 차례로 방문한다.
        {
            if (visited[next]) continue;// 이미 방문한 정점이면 다음 정점
            visited[next] = order++;// 방문하면 order 값을 증가
            q.push(next);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    std::cin >> N >> M >> R;
    // 인접 리스트(vector<vector<int>>)로 초기화
    map = vector<vector<int>>(N + 1);
    for(int i = 0; i < M; i++)
    {
        int a, b;
        std::cin >> a >> b;
        map[a].push_back(b);// 해당 a 값에 vector에 b 값을 추가
        map[b].push_back(a);// 무방향 간선이므로 b에도 a 값 추가
    }
    // 모든 인접 정접들은 정렬
    for(int i = 1; i <= N; i++)
    {
        sort(map[i].begin(), map[i].end());
    }
    // Dfs 시작
    bfs(R);
    // 모든 정점을 방문 했으므로 각 정점별 visited 방문 순서를 출력
    for (int i = 1; i <= N; i++)
    {
        std::cout << visited[i] << "\n";
    }
    return 0;
}

배운 점과 결론

이번 문제를 통해 BFS를 활용한 그래프 탐색에서 방문 순서를 기록하는 방법을 배울 수 있었습니다.

 

1, BFS의 효율성

• BFS는 최단 거리로 정점을 탐색하며, 가까운 정점부터 방문합니다. 큐를 사용해 순차적으로 탐색할 수 있어 효율적이며, 탐색 순서가 일정합니다.

2, 오름차순 방문과 정렬

• 인접 정점을 오름차순으로 방문해야 하는 조건을 만족하기 위해 인접 리스트를 오름차순으로 정렬하였습니다. 이 과정 덕분에 방문 순서가 일정해졌습니다.

3, 방문 순서 기록의 중요성

• order 변수를 통해 방문 순서를 기록함으로써, 문제에서 요구하는 각 정점의 방문 순서를 정확히 출력할 수 있었습니다. 또한, 시작 정점에서 도달할 수 없는 정점은 visited 배열이 초기값 0을 유지하므로, 연결 여부를 확인하는 데 유용했습니다.

결론

이 문제를 통해 BFS 탐색의 큐 활용 방식과 순서 기록을 배웠고, 다양한 그래프 탐색 문제에 응용할 수 있는 기법을 익혔습니다. 앞으로는 BFS에서 오름차순 방문이 필요할 때는 인접 리스트 정렬을 기억하고, 방문 순서를 기록하는 습관을 갖추어야겠다고 느꼈습니다.