[자바] 백준 17412 - 도시 왕복하기 1 (java)

 문제 : boj17412

---

 

필요 알고리즘 개념

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

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

 

---

 

풀이

  내 경우엔 에드몬드-카프 알고리즘을 사용해 최대 유량을 구했다. 완전 기본 형태의 문제로, 간선이 존재하는 방향으로 용량(capacity)을 1로 잡고 알고리즘을 구현해주면 된다.

 

 

---

 

코드 : github

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

public class Main {
    private static final int SOURCE = 1;
    private static final int SINK = 2;
    int[][] capacity, flow;

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        capacity = new int[n+1][n+1];
        flow = new int[n+1][n+1];
        ArrayList<Integer>[] edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        while (p-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            capacity[a][b] = 1;
            edges[a].add(b);
            edges[b].add(a);
        }

        long cnt = 0;
        while (true) {
            int[] parent = new int[n+1];
            Arrays.fill(parent, -1);
            Queue<Integer> q = new ArrayDeque<>();
            parent[SOURCE] = SOURCE;
            q.add(SOURCE);

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

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

            cnt += minFlow;
        }
        System.out.println(cnt);
    }

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