[BOJ] 백준 28040 - Asking for Money

문제 정보

사용 알고리즘

그래프(Graph)
그래프 탐색(Graph Search)
깊이 우선 탐색(DFS)

문제

$N$명의 사람들이 있고, 각자 돈을 빌릴 수 있는 두 명이 주어집니다. 이때, $N$명의 사람 중 한 명에게 외부에서 돈을 빌려달라고 요청합니다. 이제 다음을 반복합니다.

만약, $i$번 사람이 돈을 빌려달라는 요청을 처음 받았다면 돈을 빌려줍니다.
돈을 빌려준 이후, 자신이 돈을 빌릴 수 있는 두 명에게 돈을 빌려달라는 요청을 보냅니다.
돈을 빌릴 수 있는 두 명 모두 이미 다른 사람에게 돈을 빌려달라는 요청을 받았다면, $i$번 사람은 돈을 받지 못하므로 돈을 잃습니다.
이 때, 두 명 모두에게 빌려달라는 요청을 해 두 명 모두에게 돈을 받을 수도 있습니다.
또한, 돈을 빌려달라는 요청이 오는 즉시 돈을 빌려주어야 하지만, 돈을 빌려달라는 요청을 보내는 순서는 상관 없습니다.

이제, $N$명의 사람 각각에 대해 모든 경우에 있어 돈을 잃는 경우가 없다면 N을, 그렇지 않고 한 가지 경우라도 돈을 잃을 수 있다면 Y를 출력합니다.

문제 간략화

모든 정점의 out-degree가 $2$인 $N$개의 정점으로 이루어진 방향 그래프가 주어집니다. 모든 $i$번 정점에 대해 원하는 하나의 정점에서 시작해 원하는 순서로(이미 탐색된 정점들의 인접 정점들 중 임의로 다음 정점을 고름) 탐색을 할 때, $i$번 정점을 탐색하였을 때, $i$번 정점에서 나가는 방향으로 직접 연결된 두 정점이 이미 탐색된 상태로 할 수 있는지 판단하는 문제입니다.

문제 제한

$3 \leq N \leq 1000$
$i$번 정점에서 나가는 다음 정점은 $i$가 아니며, 서로 다르다.

풀이

$i$번 정점에서 나가는 두 정점 $X_i, Y_i$에 대해 단 하나의 경우라도 $X_i, Y_i$가 모두 탐색되었는 지 보면 됩니다. 즉, $i$번 정점에 대한 최악의 경우를 생각하면, 어떤 정점에서 탐색을 시작하여 최대한 늦게 마지막으로 $i$번 정점을 탐색하였을 때, $i$번 정점에서 나가는 두 정점이 모두 탐색되게 할 수 있는 지 판단하면 됩니다.

즉, 이는 다음과 같은 조건으로 바뀌게 됩니다.

모든 $i$번 정점에 대해 순서대로 다음 조건을 만족하는 $v_i\ne i$가 존재하면 Y를, 그렇지 않으면 N을 출력합니다.

$v_i$에서 출발해서 $i$번 정점을 탐색할 수 있어야 합니다.

$v_i$에서 출발해서 $i$번 정점을 거치지 않고 $X_i$와 $Y_i$를 모두 탐색할 수 있어야 합니다.

이를 나이브하게 구현한다면 $O(N)$개의 정점에 대해, $O(N)$개의 출발 정점을 설정하여 $O(N)$의 DFS 혹은 BFS를 수행해야 하므로, $O(N^3)$의 시간복잡도를 가지게 됩니다. 그러나 시간 제한이 $0.5$초이므로 시간 복잡도를 줄여야 합니다.

정점 $a$에서 출발하여 $b$번 정점을 거치지 않고 $c$에 도착할 수 있는 지를 판단하는 것은 역방향 간선 그래프에서, $c$번 정점에서 출발하여 $b$번 정점을 거치지 않고 $a$에 도착할 수 있는 지를 판단하는 것과 동일합니다. $c$와 $b$가 정해져 있다면, 탐색 가능한 모든 $a$를 $O(N)$의 시간 복잡도에 한번에 찾을 수 있습니다.

즉, 위의 조건을 역방향 그래프 상에서 다음 동치 명제로 바꿀 수 있습니다.

모든 $i$번 정점에 대해 순서대로 다음 조건을 만족하는 $v_i\ne i$가 존재하면 Y를, 그렇지 않으면 N을 출력합니다.

$i$번 정점에서 출발하여 $v_i$에 도착할 수 있어야 합니다.

$X_i$에서 출발해서 $i$번 정점을 거치지 않고 $v_i$에 도착할 수 있어야 합니다.

$Y_i$에서 출발해서 $i$번 정점을 거치지 않고 $v_i$에 도착할 수 있어야 합니다.

즉, 역방향 간선 그래프를 만들어, $i$번 정점에 대하여 $i$, $X_i$, $Y_i$에 대해 DFS를 수행하여 얻은 세개의 정점집합의 교집합이 공집합이 아니라면 Y를, 그렇지 않으면 N을 출력하면 됩니다. $O(N)$개의 정점에 대해, $3$개의 출발 정점을 설정하여 $O(N)$의 DFS 혹은 BFS를 수행해야 하므로, $O(N^2)$의 시간복잡도에 문제를 해결할 수 있습니다.

구현

먼저 그래프를 받고 역방향 그래프를 만들었습니다. 이후 시작 정점과 제외할 정점을 인자로 받아, 시작 정점에서 출발하여 제외할 정점을 제외하고 도달할 수 있는 정점들을 반환하는 dfs 함수를 작성하였습니다. 제외할 정점이 없을 때는 -1을 인자로 넘겨주었습니다.

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

void solve() {
    int i,j;
    int n;
    cin>>n;
    vector<pair<int,int>>grp(n+1);
    vector<vector<int>>rgrp(n+1);
    string ans;
    for(i=1;i<=n;i++){
        cin>>grp[i].first>>grp[i].second;
        rgrp[grp[i].first].push_back(i);
        rgrp[grp[i].second].push_back(i);
    }
    function<vector<bool>(int,int)> dfs=
            [&rgrp,&n](int s, int inter)->vector<bool>{
        stack<int>stk;
        stk.push(s);
        vector<bool>vis(n+1);
        vis[s]=1;
        while(stk.size()){
            int now=stk.top();
            stk.pop();
            for(auto k:rgrp[now]){
                if(vis[k]||k==inter)continue;
                else{
                    vis[k]=1;
                    stk.push(k);
                }
            }
        }
        return vis;
    };
    for(i=1;i<=n;i++){
        auto vis1=dfs(grp[i].first,i);
        auto vis2=dfs(grp[i].second,i);
        auto vis3=dfs(i,-1);
        for(j=1;j<=n;j++){
            if(vis1[j]&&vis2[j]&&vis3[j]){
                ans+='Y';
                break;
            }
        }
        if(j==n+1)ans+='N';
    }
    cout<<ans;
}

int main() {
#ifdef kidw0124
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(0)->sync_with_stdio(0);
#endif
    int t = 1;
    //cin >> t;
    while (t--) solve();
}