[자바] 백준 6086 - 최대 유량 (java)

 문제 : boj6086

---

 

필요 알고리즘 개념

• 네트워크 플로우 (최대 유량)
  
  • 최대 유량 기본 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  내 경우엔 에드몬드-카프 알고리즘을 사용해 최대 유량을 구했다. 에드몬드-카프 알고리즘을 적용할 수 있는 기본 문제로, 별도로 구현에 대해서는 풀이하지 않는다.

 

  주의점은 입력으로 들어온 간선의 용량(capacity)이 양방향이라는 점이다. 즉, 'A B 3'과 함께 'B A 3'도 들어올 수 있다. 이 경우 A와 B 사이의 용량은 중복된 입력의 합계가 되어야 한다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static final int SOURCE = 'A'-'A';
    private static final int SINK = 'Z'-'A';
    private static final int A_TO_Z = 'Z'-'A'+1;
    private static final int LIMIT_OF_IDX = ('Z'-'A'+1)*2;

    private int charToIdx(char c) {
        if (c <= 'Z') return c-'A';
        return c-'a'+A_TO_Z;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] capacity = new int[LIMIT_OF_IDX][LIMIT_OF_IDX];
        int[][] flow = new int[LIMIT_OF_IDX][LIMIT_OF_IDX];
        ArrayList<Integer>[] edges = new ArrayList[LIMIT_OF_IDX];
        for (int i = 0; i < LIMIT_OF_IDX; i++) edges[i] = new ArrayList<>();

        while (n-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = charToIdx(st.nextToken().charAt(0));
            int b = charToIdx(st.nextToken().charAt(0));
            int c = Integer.parseInt(st.nextToken());
            capacity[a][b] += c;
            capacity[b][a] += c;
            edges[a].add(b);
            edges[b].add(a);
        }

        int sum = 0;
        while (true) {
            int[] parents = new int[LIMIT_OF_IDX];
            Arrays.fill(parents, -1);
            Queue<Integer> q = new ArrayDeque<>();
            q.add(SOURCE);
            parents[SOURCE] = SOURCE;

            while (!q.isEmpty() && parents[SINK] == -1) {
                int cur = q.poll();
                for (int next : edges[cur]) {
                    if (parents[next] == -1 && capacity[cur][next] - flow[cur][next] > 0) {
                        q.add(next);
                        parents[next] = cur;
                    }
                }
            }

            if (parents[SINK] == -1) break;

            int min = Integer.MAX_VALUE;
            for (int i = SINK; i != SOURCE; i = parents[i]) {
                min = Math.min(min, capacity[parents[i]][i] - flow[parents[i]][i]);
            }

            for (int i = SINK; i != SOURCE; i = parents[i]) {
                flow[parents[i]][i] += min;
                flow[i][parents[i]] -= min;
            }
            sum += min;
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}