백준 21606번 [아침 산책](C++) -yes6686- 티스토리

백준 문제 풀이: 21606 [아침 산책]

---

문제 링크: https://www.acmicpc.net/problem/21606

문제 설명:

그래프로 주어진 지도에서, 실내와 실외의 노드를 기반으로 산책 루트를 계산하는 문제입니다. 실내 노드에서 시작하여 다른 실내 노드로 가는 모든 가능한 경로를 찾아야 합니다. 그래프에서 실내 노드끼리는 직접 연결되고, 실외 노드는 경유지로만 사용됩니다.

목표는 실내 노드 사이의 경로를 계산하여 출력하는 것입니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int arr[200001]; // 노드 타입 저장 (0: 실외, 1: 실내)
vector v[200001]; // 인접 리스트
queue q; // BFS를 위한 큐
int visited[200001]; // 방문 체크
int ans; // 총 경로 수
int cnt; // 현재 실내 노드 개수

// DFS를 사용하여 연결된 노드 탐색
void dfs(int start, int current) {
    for (int i = 0; i < v[current].size(); i++) {
        int next = v[current][i];
        if (visited[next] == 0) {
            visited[current] = 1;
            if (arr[next] == 0) { // 실외 노드
                dfs(start, next);
            } else { // 실내 노드
                cnt++;
                if (v[next].size() != 1) q.push(next);
            }
            if (start == current) {
                ans += (cnt + 1) * cnt;
                cnt = 0;
            }
        }
    }
}

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    // 노드 타입 초기화
    for (int i = 0; i < s.size(); i++) {
        arr[i + 1] = s[i] - '0';
    }

    // 그래프 입력
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    // BFS 시작점: 첫 번째 실내 노드
    for (int i = 1; i <= n; i++) {
        if (arr[i] == 1) {
            q.push(i);
            break;
        }
    }

    // BFS를 통해 모든 경로 탐색
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        dfs(current, current);
    }

    // 결과 출력
    cout << ans << '\n';

    return 0;
}

예제 입력:

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

예제 출력:

4

---

코드 설명

• 핵심 알고리즘: DFS와 BFS를 결합하여 실내 노드 간의 모든 경로를 계산합니다.
• 구현 세부사항:
  • arr[i]: 노드의 타입을 저장 (0: 실외, 1: 실내).
  • dfs: 연결된 노드를 탐색하여 실내 노드 간 경로를 계산합니다.
  • 실외 노드는 경유지로만 사용되며, 실내 노드에서 다른 실내 노드로의 경로를 모두 계산합니다.
• 시간 복잡도: O(n), n은 노드 수 (그래프 탐색).

---

결과

입력된 그래프에서 실내 노드 간의 가능한 모든 경로를 정확히 계산합니다. 문제는 그래프 탐색과 경로 계산을 연습하기에 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!