[C/C++] 백준 #2316 도시 왕복하기 2(포드-폴커슨 알고리즘)

도시를 디니면서 어떤 조건을 만족하는 문제들은 조건에 따라서 푸는 방법들이 다양합니다.  NP-Hard 문제인 세일즈맨 문제와 같이 특정 알고리즘이 없는 문제도 있지만, #2316 문제와 같이 문제를 변행해서 기존의 알고리즘을 적용할 수 있는 문제도 있습니다.

 

문제의 링크입니다.

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

2316번: 도시 왕복하기 2

 

이 문제는, 1번 도시에서 2번 도시로 이동을 하는데, 한번 방문했던 도시는 다시 방문하지 않고, 몇번 왔다갔다 할 수 있는가를 계산합니다.  문제를 보고, 이 문제가 최대 유량 문제라고 판단되었지만, 문제는 최대 유량 문제에서는 유향 그래프(directed graph)이어야 하고, 간선에 유량을 적용할 수 있어야 하는데, 이 문제는 무향 그래프이고, 노드에 1이라는 유량이 있는 것이었죠.  무향 그래프에 유량이 노드에 있는 문제를 푸는 것이 관건이라고 할 수 있습니다.

 

visiting cities

일단, 각각의 도시들은 1번부터 N번까지 노드로 표현하고, 각각의 도시들을 잇는 양방향 도로를 그래프로 표시하면 다음과 같습니다.

 

1번도시에서 2번 도시로 가는데, 중간에 도시들은 오직 1번만 방문 가능

위와 같은 그래프에서는 1번 도시가 출발점이고, 2번 도시가 도착지점입니다.  1번에서 2번으로 가는 방법과 2번에서 1번으로 가는 방법은 동등하기 때문에 1번 도시를 출발점으로 2번 도시를 도착점으로 지정해서 문제를 풀 수 있습니다.

 

중간에 경유하는 도시들은 오직 한번만 방문할 수 있기 때문에 최대유량 알고리즘하고 비슷합니다.  그런데, 노드 방문과 관련한 최대유량 알고리즘이 없어서 고민을 하였습니다.  어떻게 하면 도시가 유량 1인 조건을 가진 것으로 할 수 있을지를요.

 

일단 저 그래프에서는 1-3-2 경로와 1-4-5-2 경로의 두가지로 2번 이동이 가능합니다.  도시 방문이 제한조건이기 때문에 자동적으로 한번 사용한 간선은 다시 사용할 일은 없습니다.  즉, 이미 간선도 유량 1인 셈이 됩니다.  이 그래프를 적절하게 유향그래프로 만들면서 양방향 이동이 되게 하기 위해서는, 다음의 방법으로 유향 그래프를 만들 수 있습니다.

 

1) 각각의 도시가 단방향으로 유량 1인 간선을 내부적으로 가지게 한다.

2) 도시에는 오는 방향을 받는 진입도시와 나가는 방향만을 가지는 진출도시인 가상의 두 도시를 존재하도록 한다.

3) A 도시와 B도시 사이의 간선은, \(A_{out} \rightarrow B_{in}\) 간선과 \(B_{out} \rightarrow A_{in}\) 으로 바꾼다.

 

위에서 기술한 것에 맞추어 유향 그래프로 바꾸면 다음과 같습니다.

 

이렇게 바꾸면, 노드의 수가 2배가 되고, 간선의 수는 \(N+2E\)로 늘게 됩니다.  하지만 이렇게 함으로써 우리는 최대유량 알고리즘을 적용할 수 있습니다.

 

일단 저는 포드-폴커슨 알고리즘으로 구현했습니다.  모든 간선의 최대 유량은 1이기때문에 굳에 에드먼드-카프 알고리즘을 적용할 필요는 없습니다.  갈 수 있는 경로 탐색은 깊이 우선 탐색을 이용해서 구현했습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2316
//        - by Aubrey Choi
//        - created at 2023-04-21
//------------------------------------------------
#include <cstdio>
#include <unordered_set>
using namespace std;

unordered_set<int> *adj;
int *visited;
bool dfs(int u, int c)
{
    if(u == 4) return true;
    visited[u] = c;
    for(auto v : adj[u])
    {
        if(visited[v] == c) continue;
        if(dfs(v, c))
        {
            adj[u].erase(v);
            adj[v].insert(u);
            return true;
        }
    }
    return false;
}

int main()
{
    int n, p;
    scanf("%d%d", &n, &p);
    adj = new unordered_set<int>[n*2+2];
    visited = new int[n*2+2];
    for(int i = 2; i <= n*2; i+=2) adj[i].insert(i+1);
    for(int i = 0; i < p; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u*2+1].insert(v*2);
        adj[v*2+1].insert(u*2);
    }
    int ans = 0;
    while(dfs(3, ans+1)) ans++;
    printf("%d\n", ans);
}