백준 7616번: 교실로 가는 길 (Java)

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

7616번: 교실로 가는 길

 

 

 

 

 

 

 

 

---

 

풀이

백준 2316번처럼 간선 뿐만 아니라 정점도 최대 한 번만 방문할 수 있으므로, '정점 분할'을 해 줍니다.

에드몬드-카프로 유량이 K 이상인지(==경로가 K개 이상인지) 확인하여, K개 이상일 경우 경로를 출력해줍니다. 유의할 점으로는, 에드몬드-카프에서 찾은 K개 증가 경로를 역추적하여 출력할 경우 제대로 된 결과가 나오지 않을 수 있습니다.

2 6
3 5
4 6
1 4 6
2 3 5
1 4
2 3

0 0 

같은 경우가 반례가 됩니다. 시간이 나면 그림으로 예시를 추가하도록 하겠습니다.

 

대신, source에서부터 시작하여, 유량이 흐르는 간선을 따라 sink까지 도달하는 경로 K개를 찾으면 됩니다. 방문한 간선은유량을 1 줄여주어, 경로가 중복되지 않도록 합니다.

 

 

배운 점

유량이 1이며 정점을 중복 방문하지 못하는 그래프의 에드몬즈-카프 알고리즘에서 경로 추적하는 방법을 배웠습니다.

알고리즘 자체가 제 역량 이상이다보니, 사소한 부분에서부터 실수가 잦았습니다. 조금 더 차분할 필요가 있습니다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int[][] capacity;
    static int[][] flow;
    static StringBuilder sb = new StringBuilder();
    static List<List<Integer>> graph;
    static int N, K;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = 0;
        while (((K=Integer.parseInt(st.nextToken())) != 0)) {
            T++;
            N = Integer.parseInt(st.nextToken());
            graph = new ArrayList<>();
            for (int i = 0; i <= 2*N; i++) {
                graph.add(new ArrayList<Integer>());
            }
            capacity = new int[2*N+1][2*N+1];
            flow = new int[2*N+1][2*N+1];
            // Note: 입력값이 대칭적으로 주어짐
            for (int i = 1; i <= N; i++) {
                st = new StringTokenizer(br.readLine());
                int cur = 2*i-1;
                graph.get(cur).add(cur+1);
                graph.get(cur+1).add(cur);
                capacity[cur][cur+1] = 1;
                while (st.hasMoreTokens()) {
                    int to = 2*Integer.parseInt(st.nextToken())-1;
                    graph.get(cur+1).add(to);
                    graph.get(to).add(cur+1);
                    capacity[cur+1][to]+=1;
                }
            }
            sb.append("Case "+T+":\n");
            maximumFlow(2, 3);
            sb.append("\n");
            st = new StringTokenizer(br.readLine());
        }
        System.out.println(sb.toString());
    }
    
    static void maximumFlow(int source, int sink) {
        int totalFlow = 0;
        StringBuilder sb1 = new StringBuilder();
        while (true) {
            int[] parent = new int[2*N+1];
            Queue<Integer> queue = new ArrayDeque<>();
            queue.offer(source);
            parent[source] = source;
            while (!queue.isEmpty() && parent[sink] == 0) {
                int cur = queue.poll();
                for (int nxt: graph.get(cur)) {
                    if (parent[nxt] == 0 && capacity[cur][nxt] - flow[cur][nxt] > 0) {
                        parent[nxt] = cur;
                        queue.offer(nxt);
                    }
                }
            }
            
            if (parent[sink] == 0) break;
            
            // 증가하는 유량은 언제나 1
            for (int cur = sink; cur != source; cur = parent[cur]) {
                flow[parent[cur]][cur]++;
                flow[cur][parent[cur]]--;
            }
            totalFlow++;
        }
 
        if (totalFlow < K) {
            sb.append("Impossible\n");
        } else {
            for (int k = 0; k < K; k++) {
                sb.append("1 ");
                int cur = 2;
                // source에서부터 시작, K개의 경로를 찾는다.
                while (cur != sink) {
                    for (int nxt: graph.get(cur)) {
                        if (flow[cur][nxt] > 0) {
                            flow[cur][nxt]--;
                            cur = nxt;
                            if (cur % 2 == 1) sb.append((cur+1)/2+" ");
                        }
                    }
                }
                sb.append("\n");
            }
        }
    }
}