Algorithm/BOJ

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

Rubi ❤️ 2025. 5. 8. 16:59
728x90
반응형

🔍 문제 요약

  • 문제링크 : [백준 24444번]
  • 주요 태그 : BFS, 너비 우선 탐색

정점 N개, 간선 M개로 구성된 무방향 그래프가 주어졌을때,  시작 정점 R에서 너비 우선 탐색(BFS)을 수행하고, 각 정점의 방문 순서를 출력한다. 인접 정점은 오름차순으로 방문해야 하며, 시작 정점에서 도달할 수 없는 정점은 0을 출력한다.

💡 문제 분석

  • 그래프가 무방향이며, 인접 정점은 오름차순으로 방문해야 한다.
  • 정점의 수는 최대 100,000개, 간선은 200,000개 → O(N + M)
  • BFS를 이용하되, 방문 순서를 기록해야 하므로 단순 방문 여부가 아닌 방문 순서 배열을 사용해야 한다.

🔑 아이디어

  • 그래프 표현: 인접 리스트 (vector<vector<int>>)
  • 방문 순서 기록: visited[i] = 방문 순서
  • BFS 구현: 큐(queue<int>) 사용
  • 오름차순 방문 보장: 각 정점의 인접 리스트를 정렬

🧩 풀이 전략

  1. 정점 수 N, 간선 수 M, 시작 정점 R 입력
  2. 간선을 인접 리스트로 저장 (양방향)
  3. 각 정점의 인접 정점 리스트 정렬
  4. BFS 수행:
    • 시작 정점을 큐에 넣고 방문 순서를 1로 설정
    • 큐에서 하나씩 꺼내면서 인접 정점 중 방문하지 않은 정점을 큐에 추가하며 순서 증가
  5. 1번부터 N번까지 각 정점의 방문 순서 출력

📦 예제 입력 & 출력

  • 입력
5 5 1
1 4
1 2
2 3
2 4
3 4
  • 출력
1
2
4
3
0

🖥️ 코드

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

using namespace std;

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

    int N, M, R;
    cin >> N >> M >> R;

    vector<vector<int>> graph(N + 1);
    vector<int> visited(N + 1, 0); // 방문 순서 저장

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // 무방향 그래프
    }

    // 인접 정점 오름차순 방문을 위해 정렬
    for (int i = 1; i <= N; ++i)
        sort(graph[i].begin(), graph[i].end());

    queue<int> q;
    int order = 1;
    q.push(R);
    visited[R] = order++;

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int next : graph[cur]) {
            if (visited[next] == 0) {
                visited[next] = order++;
                q.push(next);
            }
        }
    }

    for (int i = 1; i <= N; ++i)
        cout << visited[i] << "\n";

    return 0;
}

✅ 검증 및 테스트

  • 정점이 연결되어 있지 않을 경우 → 방문 순서가 0으로 출력되는지 확인
  • 간선 입력 순서가 정렬되어 있지 않을 경우 → 정렬 후 오름차순 탐색 확인
  • 중복 간선 없음 조건은 입력으로 보장됨

⏱️ 시간복잡도

  • N (5 ≤ N ≤ 100,000), M (1 ≤ M ≤ 200,000),  R (1 ≤ R ≤ N)
  • 그래프 입력: O(M)O(M)
  • 인접 리스트 정렬: O(Nlog⁡D)O(N \log D), D = 평균 연결 수
  • BFS 탐색: O(N+M)O(N + M)
  • 총합: O(N + M + N log D) → 충분히 1초 통과 가능

✨ 결론

  • 이 문제는 BFS 탐색의 기본을 정확히 묻는 문제로,
    오름차순 탐색과 방문 순서 기록이라는 두 가지 디테일이 중요하다. 
  • visited[] 배열을 단순 bool로 사용하지 않고 순서를 기록하는 배열로 사용하면 다양한 BFS 응용 문제에도 확장할 수 있다.
  • 문제 조건을 꼼꼼히 읽고 구현할 것.

 

728x90

 

728x90
반응형