[백준 6086] 최대 유량

문제 링크: https://www.acmicpc.net/problem/6086

---

풀이

에드몬드-카프 알고리즘을 이용하는 문제였다.
처음 보는 유형의 알고리즘이라 좀 힘들었지만, 문제를 풀고 나니 어떤 방식의 알고리즘인지 감을 잡을 수 있었다.

 

1. (BFS를 통해 시작점에서 도착점까지의 경로를 구한다. (경로를 구해야 하므로, 중간에 방문하는 노드를 기록해야 한다)
2. 도착점에 도달하면 BFS를 종료하고, 도착점에서 시작점까지의 경로를 거슬러 가며 최대 유량을 구한다.
3. 도착점에서 시작점까지 다시 거슬러가면서 파이프의 잔여 용량을 갱신한다. (파이프의 잔여 용량 = 파이프의 기존 용량 - (2)에서 구한 최대 유량)

시작점~도착점까지의 경로가 존재하지 않을 때까지 1~3을 반복한다. 최대 유량의 누적합이 정답이 된다.

 

자잘한 내용을 빼고 정리하면 위와 같이 요약할 수 있을 것 같다.

(0) 입력 받기

입력 받기 파트를 따로 작성하는 이유?

 

 

^^...!
뭐가 문제지? 싶었는데 알파벳이 소문자일 수도 있다는 걸 깨달았다.
A랑 a는 다른 노드였던 거예요.

 

static int N, MAX = 52, START = 0, END = 'Z'-'A';
static int[][] pipe = new int[MAX][MAX];

static int charToInt(char c) {
    if('A'<=c && c<='Z') return c-'A';
    if('a'<=c && c<='z') return c-'a'+26;
    return -1;
}

 

파이프의 잔여 용량은 인접 행렬로 저장했고, char형을 int형으로 변환하는 함수를 만들어서 노드의 이름이 인덱스로 사용될 수 있게 했다.

입력받을때 주의해야 할 점이 또 하나 있는데, 양방향 그래프이기 때문에 pipe[a][b]=3 이면 pipe[b][a]도 3이다.

 

(1) BFS를 통해 시작점 ~ 도착점 경로 구하기

 

static void bfs(int start, int end) {
    Queue<Integer> q = new ArrayDeque<>();
    q.add(start);
    prev[start] = start; // 시작점을 큐에 push

    while(!q.isEmpty()) {
        int now = q.poll();
        if(now==end) break;
        for (int next=0; next<pipe[now].length; next++) {
            // 파이프 용량이 남아있고, 방문하지 않았던 노드라면 큐에 push
            if(pipe[now][next]>0 && prev[next]==-1) {
                q.add(next);
                prev[next] = now;
            }
        }
    }
}

 

일반적인 BFS와 다른 점은 (1) 용량이 꽉 찬 파이프는 지나갈 수 없으며, (2) 지나온 경로가 필요하다는 점이다. 그래서 직전에 방문했던 노드를 저장하는 배열 prev를 선언하여 -1로 초기화한 다음,방문체크 및 경로 기록용으로 사용했다.

 

(2) 최대 유량 구하기

 

int water = Integer.MAX_VALUE;

int now = end;
while(now!=start) {
    water = Math.min(pipe[prev[now]][now], water);
    now = prev[now];
}

 

이제 도착점에서 시작점까지 거슬러 올라가면서, 파이프의 최소 잔여 용량을 구해주면 된다.
이전 노드에서 현재 노드로 오는 파이프의 잔여 유량과, 내가 갖고 있는 최대 유량값을 비교해주며 갱신한다.

 

(3) 파이프의 잔여 용량 갱신

 

now = end;
while(now!=start) {
    pipe[prev[now]][now]-=water;
    pipe[now][prev[now]]+=water;
    now = prev[now];
}

이제 도착점에서 시작점까지 거슬러 올라가며 파이프의 잔여 용량을 갱신해줄 차례이다.

조금 어려울 수도 있는 부분인데, 유량은 방향이 존재한다.

A → B로 2만큼의 물이 흐르고 있고, B → A로 3만큼의 물이 흐르고 있다고 가정해보자.
A → B로 흐르는 물과 B → A로 흐르는 물이 상쇄되어, 결국에는 B → A로 1만큼의 물이 흐르는 상태가 된다.

 

이걸 파이프의 잔여 용량에 반영하려면 어떻게 해야할까?

pipe[a][b] = 3 이고, pipe[b][a] = 3인 상황을 생각해보자. 이 상황에서 a → b로 2만큼의 물이 흐르기 시작했다면?

 

a → b 파이프에는 1만큼의 물이 흐를 수 있겠지만, b → a에는 5만큼의 물이 흐를 수 있게 된다. 물의 용량이 3을 넘어가도, a → b로 흐르는 물이 상쇄해주기 때문이다.

이전 노드 → 현재 노드 파이프의 용량에서 water만큼을 뺐다면, 현재 노드 → 이전 노드 파이프의 용량에는 water만큼 더해주면 되는 것이다. 그리고 정답은 매번 구한 water들을 더한 값이 된다.

---

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_6086_최대유량 {
    static int N, MAX = 52, START = 0, END = 'Z'-'A';
    static int[][] pipe = new int[MAX][MAX];
    static int[] prev = new int[MAX];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = charToInt(st.nextToken().charAt(0));
            int b = charToInt(st.nextToken().charAt(0));
            int width = Integer.parseInt(st.nextToken());
            pipe[a][b] += width;
            pipe[b][a] += width;
        }

        int answer = 0;
        while(true) {
            // 이전에 구한 경로가 남아있으면 안되므로, 매번 초기화
            Arrays.fill(prev, -1);

            bfs(START,END);
            // 도착점까지 가는 경로가 없으면 반복문 탈출
            if(prev[END]==-1) break;
            answer += calculateFlow(START,END);
        }

        System.out.println(answer);
    }

    static void bfs(int start, int end) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        prev[start] = start;

        while(!q.isEmpty()) {
            int now = q.poll();
            if(now==end) break;
            for (int next=0; next<pipe[now].length; next++) {
                if(pipe[now][next]>0 && prev[next]==-1) {
                    q.add(next);
                    prev[next] = now;
                }
            }
        }
    }

    static int calculateFlow(int start, int end) {
        int water = Integer.MAX_VALUE;

        int now = end;
        while(now!=start) {
            water = Math.min(pipe[prev[now]][now], water);
            now = prev[now];
        }
        now = end;
        while(now!=start) {
            pipe[prev[now]][now]-=water;
            pipe[now][prev[now]]+=water;
            now = prev[now];
        }
        return water;
    }

    static int charToInt(char c) {
        if('A'<=c && c<='Z') return c-'A';
        if('a'<=c && c<='z') return c-'a'+26;
        return -1;
    }
}