[알고리즘 문제] 2316번 도시 왕복하기 2

출처 : https://www.acmicpc.net/problem/2316

 

1. 아이디어 접근

기존의 네트워크 플로우 문제와 달리 추가된 조건이 한 가지 더 존재한다. 그것은 바로 "지난 노드는 더 지날 수 없다" 해당 조건을 구현하기 위해서 기존의 네트워크 플로우와 달리 이상한 방향으로 계획을 세우곤 했는데 해당 문제는 어떤 예제 상황에서 힌트를 얻을 수 있었다. 

 

모든 간선의 최대 용량이 1일 때 1->2 로 가는 최대 유량은 2일 것이다. 하지만 우리가 구하고 싶은 답은 1이다. 여기서 우리가 관찰할 수 있는 것은 3으로 가나 4으로 가나 결국 5라는 공통된 지점이 존재하며 공통된 지점을 지날 때 연산 결과가 답을 도출한다는 결론을 내릴 수 있다. 

 

해당 예시에서 5번은 검문소 혹은 공항과도 같다. 여러 곳에서 한 곳에 모여서 검사하고 지나가는 상황을 생각해볼 수 있다. 그리고 그 과정에서 오직 1개만이 지나갈 수 있도록 검사하는 것이다. 만약 1개를 초과하여 존재할 경우 다른 곳으로 보내야한다. 만약 그렇다면 검문소가 모든 노드에 존재한다면 어떨까? 

 

 

일부분을 확대해서 본다면 이렇게 보일 것이다. 4와 4`의 최대 용량이 1이면 결국 4라는 큰 노드(간선이 아니라) 의 용량이 1이 된다고 표현할 수 있다. 

 

2. 코드 

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

#define SIZE 405 * 2

int N, P, c[SIZE][SIZE], f[SIZE][SIZE], ans;
vector<int> v[SIZE];

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

    cin >> N >> P;
    int x, y;
    for(int i=0;i<P;i++){
        cin >> x >> y;
        v[x].push_back(y+400); v[y].push_back(x+400);
        v[y+400].push_back(x); v[x+400].push_back(y);
        c[x][y+400] = 1, c[y][x+400] = 1;
    }
    for(int i=1; i<=N;i++){
        v[i+400].push_back(i);
        c[i+400][i] = 1;
    }
    while(1){
        queue<int> q;
        int prev[SIZE] = {0,};
        q.push(1);
        while(!q.empty() && !prev[2]){
            int loc = q.front(); q.pop();
            for(auto&i:v[loc]){
                int e = i;
                if(c[loc][i] - f[loc][i] > 0 && !prev[i]){
                    prev[i] = loc; q.push(i);
                    if(i == 402) break;
                }
            }
        }
        if(!prev[402]) break;
        for(int i=402; i!=1;i=prev[i]){
            f[prev[i]][i] += 1, f[i][prev[i]] -= 1;
            //cout << i << " ";
        }
        //cout <<"\n";
        ans++;
    }
    cout <<ans;
}

해당 코드에서 `n 은 n+400 꼴로 indexing 하였으며 구현하는 데 주의할 점은 노드에서 다른 노드는 양방향 간선이지만 같은 노드, 즉 n -> `n 은 단방향 간선임을 명심하자!

 

 

오늘은 네트워크 플로우, 최대 유량 알고리즘의 활용 문제를 풀어봤는데요, 잘 감이 안왔는데... 몇 예제도 만들어보고 하면서 "검문소" 라는 것을 정의 내리고 노드를 2개로 나눈다는 아이디어를 얻을 수 있었습니다. 

 

그 후에 까다로웠던 점은 "간선의 방향성" 이였는데요... 처음에는 모든 간선을 양방향으로 해줬지만 잘~생각해보니 같은 노드 안에서는 단방향으로 하는 것이 맞는 것 같습니다. 즉 출입문, 출입구 개념으로 적용해야 한다는 것이죠. 암튼 아이디어도 재밌었고 간단하면서 심오한 테크닉 이었던 것 같습니다.