[BOJ 34679 // C++] 홍수

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 34679번 문제인 홍수이다.
문제는 아래 링크를 확인하자.

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

 

주어진 문제의 상황을 각 하수구를 노드로, 물이 흐를 수 있는 두 하수구의 관계를 방향이 있는 에지로 하는 그래프로 모델링해보자. 이와 같은 모델에서 주어진 문제는 그래프의 모든 노드에서 입력으로 주어진 "물이 고이지 않는 하수구" 노드 중 적어도 하나에 도달할 수 있는지를 판단하는 것으로 해결할 수 있게 된다.

 

그러나 각 노드마다 "물이 고이지 않는 하수구"에 도달할 수 있는지 한 번씩 탐색해보는 것은 비효율적이다. 특히, 잘 구성된 일자 그래프가 주어지면 시간초과가 발생하게 된다. 다른 방법을 생각해보자.

 

각 노드에서 어떤 "물이 고이지 않는 하수구"에 도달할 수 있다는 것은, 주어진 그래프와 간선의 방향을 뒤집은 그래프(Transpose Graph라고 부른다)에서 각 노드마다 도달할 수 있는 "물이 고이지 않는 하수구"가 적어도 하나씩 있다는 것과 같다는 점을 관찰하자. 따라서, 주어진 "물이 고이지 않는 하수구" 노드로부터 도달할 수 있는 노드의 집합이 전체 노드의 집합과 같은지를 판단하는 것으로 문제를 해결할 수 있다.

 

이와 같은 문제 상황은 multisource BFS 등으로 어렵지 않게 해결할 수 있다. 글쓴이는 그냥 스택을 이용하여 그래프 탐색을 진행하였다.

 

높이가 같은 두 하수구 사이에서는 배수로가 있어도 어떠한 방향 에지도 생성되지 않는다는 점에 주의하자.

 

아래는 제출한 소스코드이다.

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

int N, M, K;
int H[200001];
bool visited[200001];
vector<int> G[200001];
vector<int> stk;

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

    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> H[i];
    while (M--) {
        int x, y; cin >> x >> y;
        if (H[x] > H[y]) G[y].emplace_back(x);
        else if (H[x] < H[y]) G[x].emplace_back(y);
    }

    cin >> K;
    while (K--) {
        int x; cin >> x;
        visited[x] = 1;
        stk.emplace_back(x);
    }
    while (!stk.empty()) {
        int x = stk.back(); stk.pop_back();
        for (auto &nxt:G[x]) {
            if (visited[nxt]) continue;
            visited[nxt] = 1;
            stk.emplace_back(nxt);
        }
    }
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) cout << "flood", exit(0);
    }
    cout << "no flood";
}