[C++] 2316번 도시 왕복하기 2 - 그래프 이론, 최대 유량

도시 왕복하기 2를 풀면서 같이 푼 문제라서 함께 풀이합니다.

 

1. 문제

• 도시 왕복하기 2: N개의 도시가 P개의 양방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 방문한 도시는 두 번 이상 방문할 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라.
• 도시 왕복하기 1: N개의 도시가 P개의 방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 지난 길은 다시 지날 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라.

<입력>

• -1- \(N(3 \leq N \leq 400)\), \(P(1 \leq P \leq 10,000)\)
• P개의 줄에 연결하는 서로 다른 두 도시 번호가 주어진다.

<출력>

• 왔다 갔다 할 수 있는 최대 횟수를 출력하라.

2. 재정의

• 도시 왕복하기 2: 양방향 그래프에서 1과 2를 왔다 갔다 할 수 있는 서로 겹치지 않는 길의 최대 개수를 구하여라
• 도시 왕복하기 1: 단방향 그래프에서 1과 2를 왔다 갔다 할 수 있는 서로 지나는 도시가 겹치지 않는 길의 최대 개수를 구하여라.

3. 해결 방법

• 도시 왕복하기 2만 설명합니다.
• u <-> v의 경우 u'->v, v'->u의 capacity를 1로 설정하고 최대 유량 알고리즘을 적용하면 최대 유량이 길의 개수이다.

4. 실수한 점, 개선할 점

• 무방향 그래프는 편도를 두 번 한 걸로 대체할 수 있는데 이때 편도 두 번은 역방향과 충돌을 일으키지 않는다.
• 역방향도 생각해야 되므로 그래프를 완성할 때 역방향도 추가해야 한다.
• N개로 갈 수 있는 길을 모두 생각하지 않고 길을 미리 찾아놓으면 시간을 많이 단축시킬 수 있다.

 

<코드>

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

const int INF = 987654321;
const int MAX_N = 401*2;

//도시의 개수 N, 길의 개수 P
int N, P;
//무방향 그래프
vector<int> Edge[MAX_N];
//용량과 유량, 최대 유량
int capacity[MAX_N][MAX_N], flow[MAX_N][MAX_N], total_flow;
//최대 유량 알고리즘 용 bfs 부모
int parent[MAX_N];

void input() {
    cin >> N >> P;
    for(int i=0; i<P; i++) {
        int u, v;
        
        cin >> u >> v;
        
        capacity[u*2][v*2-1] = 1;
        capacity[v*2][u*2-1] = 1;
    }
    for(int i=1; i<=N; i++)
        capacity[i*2-1][i*2] = 1;
}

//최대 유량 알고리즘
void MaximumFlow() {
    while(1) {
        //BFS
        memset(parent, -1, sizeof parent);
        
        queue<int> q;
        q.push(1);
        
        //최단으로 1에서 2에 도달하는 경로 찾기
        while(!q.empty() && parent[3] == -1) {
            int here = q.front(); q.pop();
            
            for(int Next=1; Next<=2*N; Next++)
                if(capacity[here][Next] - flow[here][Next] > 0 && parent[Next] == -1) {
                    q.push(Next);
                    parent[Next] = here;
                }
        }
        
        //sink까지의 경로를 못 앚았다면 더 이상 증가 경로가 없음
        if(parent[3] == -1)
            break;
            
        //증가 경로로 세로 흘려줄 유량 = 경료 중 최소 잔여 용량
        int amount = INF;
        for(int p = 3; p != 2; p = parent[p])
            amount = min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
        
        //증가 경로는 유량 증가, 역 방향 경로는 유량 감소
        for(int p = 3; p != 2; p = parent[p]) {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        
        total_flow += amount;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    //최대 유량 알고리즘
    MaximumFlow();
    
    cout << total_flow;
    
    return 0;
}

위는 모두 탐색해서 시간이 오래 걸렸고 가능한 길을 미리 탐색하면 속도를 줄일 수 있으며 이를 만족하는 코드가 있어서 아래에 링크해두었다.

 

<참조한 코드>

https://4802852.tistory.com/253

백준 2316번: 도시 왕복하기 2 (C++)

 

<최대 유량 알고리즘 1>

https://everenew.tistory.com/177

[네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘

 

<최대 유량 알고리즘 2>

https://unorderedmap.tistory.com/6

최대 유량 문제(Maximum Flow) - 에드몬드-카프 알고리즘 (Edmonds-Karp Algorithm)

 

<최대 유량 알고리즘 3>

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kks227&logNo=220804885235 

네트워크 유량(Network Flow) (수정: 2019-08-14)

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.