[BOJ] #17412 도시 왕복하기 1

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

---

최근에 공부하고 있는 최대 유량 (Maximum Flow) 관련 문제이다. 기존에 #6086번 문제를 한번 풀어봤었는데, 해당 문제를 풀어보았거나 최대 유량에 대해 알고 있으면, 플래4 난이도의 문제임에도 불구하고 쉽게 해결할 수 있다.

최대 유량을 해결하는 알고리즘으로는 다음의 방법이 있다. PS에서의 최대 유량은 보통 이걸 많이 사용하는 듯 하다.

 

Max Flow : 에드먼드-카프 알고리즘(Edmonds-Karp Algorithm):

• 포드-풀커슨 알고리즘의 BFS 버전: 포드-풀커슨 알고리즘을 BFS를 사용하여 구현한 것으로, 증강 경로를 찾는 데 BFS를 사용하여 최단 경로를 선택합니다.

• 시간 복잡도: O(V * E^2), 여기서 V는 노드의 개수입니다. 이 알고리즘은 보장된 시간 복잡도를 가지며, 실용적인 환경에서 널리 사용됩니다.

 

이 문제의 해법은 문제 자체에 나와있다. "이때 한 경로에 포함된 길이 다른 경로에 포함되면 안된다." 간선 재사용이 불가능하다는 것이다. 그 말인 즉 주어진 그래프가 capacity가 1짜리 간선으로 구성된 그래프임을 인지하고 해당 용량에 따라 1번 도시에서 2번 도시로 가는 최대 유량을 구해주면 된다. 이 외에는 따로 적용된 스킬이나 응용은 없는 듯 했다. 그냥 에드먼드-카프 알고리즘의 정형화 된 코드를 그대로 적용하면 해결할 수 있다.

---

#include <iostream>
#include <vector>
#include <queue>

#define MAX 402
#define INF 999999

using namespace std;

int N,P, total=0;
int capacity[MAX][MAX], flow[MAX][MAX], visited[MAX];
vector<int> v[MAX];

void maxFlow(int start, int end) {
    while (1) {
        fill(visited, visited+MAX, -1);

        queue<int> q;
        q.push(start);

        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            for (int next : v[curr]) {
                if (capacity[curr][next] - flow[curr][next] > 0 && visited[next] == -1) {
                    q.push(next);
                    visited[next] = curr;

                    if (next == end) break;
                }
            }
        }

        if (visited[end] == -1) break;

        int tmp = INF;
        for (int i=end; i!=start; i=visited[i]) 
            tmp = min(tmp, capacity[visited[i]][i] - flow[visited[i]][i]);
        
        for (int i=end; i!=start; i=visited[i]) {
            flow[visited[i]][i] += tmp;
            flow[i][visited[i]] -= tmp;
        }

        total += tmp;
    }
}

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

    cin >> N >> P;

    for (int i=0; i<P; i++) {
        int from, to;
        cin >> from >> to;

        v[from].push_back(to);
        v[to].push_back(from);
        capacity[from][to] = 1;
    }

    maxFlow(1,2);

    cout << total << '\n';

    return 0;
}

---