오늘의 학습 키워드

• 그래프 탐색 (BFS)

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

• [백준] 알고리즘 수업 - 너비 우선 탐색 1 - 24444
• Silver II
• C++ 풀이
• 풀이시간: 12m

문제해설

정점 N과 간선 M이 입력으로 주어지면, 시작 정점 R에서 정점 $N_i$ 의 방문 순서를 출력하는 문제이다. 이때, 방문 순서는 깊이 우선 탐색(BFS)로 결정이 된다.
전체적인 흐름은 4일차 문제와 동일하며, 탐색 방법만 DFS에서 BFS로 바뀌었다.

접근법: 너비 우선 탐색(BFS)

그래프 표현: 인접리스트로 선택

4일차 문제와 동일.

그래프 탐색: BFS 구현

BFS 구현은 정형화된 절차이기 때문에 기계적으로 작성했다. 이미 그래프 문제를 많이 다루었기에 큰 고민 없이 빠르게 코드를 작성할 수 있었다.
항상 염두에 두어야 할 점은, 방문 시점을 Queue에서 pop할 때가 아니라 push할 때로 기준을 잡는다는 것이다. 기준을 명확히 해야 복잡한 로직에서도 논리적 오류를 줄일 수 있다.

#define MAX 100002
#include <bits/stdc++.h>
using namespace std;

int N, M, R;
vector<int> ll[MAX];
int vis[MAX];

int main(){
    // 입력 및 초기화
    memset(vis, 0, sizeof(vis));
    cin >> N >> M >> R;
    for (int i = 0; i < M; i++){
        int u, v; cin >> u >> v;
        ll[u].push_back(v), ll[v].push_back(u);
    }
    for (int i = 1; i <= N; i++) sort(ll[i].begin(), ll[i].end());
    // BFS
    int cnt = 0;
    queue<int> Q;
    vis[R] = ++cnt;
    Q.push(R);
    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        for (int next : ll[cur]){
            if (vis[next] > 0) continue;
            vis[next] = ++cnt;
            Q.push(next);
        }
    }
    // 출력
    for (int i = 1; i <= N; i++) cout << vis[i] << "\n";
    return 0;
}

오늘의 회고

BFS/DFS 문제에서 봤듯이 탐색 방법에 따라 방문 순서가 달라진다. DFS는 재귀적 사고가 필요한 반면, BFS는 Queue 자료구조를 사용해 비교적 간단하게 해결할 수 있다. DFS와 BFS 모두로 해결 가능한 문제라면, 일반적으로 BFS를 사용하는 것이 더 유리하다. DFS가 반드시 필요한 경우에만 DFS로 풀이하고, 가능한 한 BFS를 활용해야 한다.