11월 18일 - 도시 왕복하기 2[BOJ/2316]

이 문제는 네트워크 플로우 알고리즘을 사용해 두 도시(1번과 2번) 간 최대 왕복 횟수를 계산하는 문제였다. 핵심은 최대 유량(Maximum Flow) 알고리즘을 적용해 네트워크를 설계하고, 주어진 조건을 충족시키면서 최대 왕복 가능한 경로를 찾는 것이었다.

문제 접근 방법

1. 네트워크 모델링:

• 각 도시를 "in" 노드와 "out" 노드로 분리했다. 예를 들어, 도시 i는 i_in과 i_out으로 나뉜다.
• 도시 간 연결은 i_out -> j_in 형태로 모델링되며, 용량은 무한대로 설정한다. 이는 도시를 한 번 방문 후 다른 도시로 이동 가능하다는 의미다.
• 모든 도시의 i_in -> i_out 간선의 용량은 1로 설정하여 도시를 한 번만 방문하도록 제한했다.

2. 소스와 싱크 설정:

• 1번 도시의 "out" 노드를 소스(source)로 설정한다.
• 2번 도시의 "in" 노드를 싱크(sink)로 설정한다.

3. 최대 유량 계산:

• 에드몬드-카프 알고리즘(Edmonds-Karp)을 사용하여 최대 유량을 계산했다.
• 이 알고리즘은 BFS를 사용해 증가 경로를 찾고, 각 경로의 최소 잔여 용량을 계산해 유량을 업데이트한다.

코드

import java.util.*;

public class Main {
    static final int INF = 987654321; // 무한대 값 설정
    static int cityNum, pathNum, vertexNum;
    static int[][] capacity, flow;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        cityNum = sc.nextInt();
        pathNum = sc.nextInt();
        vertexNum = (cityNum + 1) * 2; // in, out 노드를 포함한 총 정점 수

        capacity = new int[vertexNum][vertexNum];
        flow = new int[vertexNum][vertexNum];

        // 각 도시의 in -> out 용량 1 설정
        for (int i = 2; i < vertexNum; i += 2) {
            capacity[i][i + 1] = 1;
        }

        // 간선 입력
        for (int i = 0; i < pathNum; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int uIn = u * 2, uOut = uIn + 1;
            int vIn = v * 2, vOut = vIn + 1;

            // u -> v, v -> u의 간선 생성
            capacity[uOut][vIn] = INF;
            capacity[vOut][uIn] = INF;
        }

        int sourceOut = (1 * 2) + 1; // 1번 도시의 out 노드
        int sinkIn = (2 * 2); // 2번 도시의 in 노드

        System.out.println(maximumFlow(sourceOut, sinkIn));
    }

    // 최대 유량 계산 (에드몬드-카프 알고리즘)
    static int maximumFlow(int source, int sink) {
        int totalFlow = 0;

        while (true) {
            int[] parent = new int[vertexNum];
            Arrays.fill(parent, -1);
            Queue<Integer> queue = new LinkedList<>();
            parent[source] = source;
            queue.add(source);

            // BFS로 증가 경로 탐색
            while (!queue.isEmpty() && parent[sink] == -1) {
                int u = queue.poll();

                for (int v = 2; v < vertexNum; v++) {
                    if (capacity[u][v] - flow[u][v] > 0 && parent[v] == -1) {
                        queue.add(v);
                        parent[v] = u;
                    }
                }
            }

            // 증가 경로가 없는 경우 종료
            if (parent[sink] == -1) {
                break;
            }

            // 경로 상의 최소 잔여 용량 계산
            int amount = INF;
            for (int p = sink; p != source; p = parent[p]) {
                amount = Math.min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
            }

            // 잔여 용량을 업데이트
            for (int p = sink; p != source; p = parent[p]) {
                flow[parent[p]][p] += amount;
                flow[p][parent[p]] -= amount;
            }

            totalFlow += amount;
        }

        return totalFlow;
    }
}

코드 설명

1. 네트워크 모델링

capacity = new int[vertexNum][vertexNum];
flow = new int[vertexNum][vertexNum];

for (int i = 2; i < vertexNum; i += 2) {
    capacity[i][i + 1] = 1; // 각 도시의 in -> out 용량 1 설정
}

• 각 도시는 "in" 노드와 "out" 노드로 분리되며, 도시 내부 이동 용량을 1로 설정해 도시를 한 번만 방문하도록 제한했다.

2. 간선 추가

for (int i = 0; i < pathNum; i++) {
    int u = sc.nextInt();
    int v = sc.nextInt();
    int uIn = u * 2, uOut = uIn + 1;
    int vIn = v * 2, vOut = vIn + 1;

    capacity[uOut][vIn] = INF; // u -> v 용량 무한대
    capacity[vOut][uIn] = INF; // v -> u 용량 무한대
}

• 도시 간 연결은 "out -> in" 방식으로 설정된다. 이때 용량은 무한대로 설정하여 제한 없이 이동할 수 있도록 했다.

3. 최대 유량 계산 (에드몬드-카프)

while (true) {
    int[] parent = new int[vertexNum];
    Arrays.fill(parent, -1);
    Queue<Integer> queue = new LinkedList<>();
    parent[source] = source;
    queue.add(source);

    while (!queue.isEmpty() && parent[sink] == -1) {
        int u = queue.poll();
        for (int v = 2; v < vertexNum; v++) {
            if (capacity[u][v] - flow[u][v] > 0 && parent[v] == -1) {
                queue.add(v);
                parent[v] = u;
            }
        }
    }

    if (parent[sink] == -1) {
        break; // 증가 경로가 없는 경우 종료
    }

    int amount = INF;
    for (int p = sink; p != source; p = parent[p]) {
        amount = Math.min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
    }

    for (int p = sink; p != source; p = parent[p]) {
        flow[parent[p]][p] += amount;
        flow[p][parent[p]] -= amount;
    }

    totalFlow += amount;
}

• BFS 탐색을 통해 증가 경로를 찾는다. 찾은 경로에서 최소 잔여 용량을 계산하고, 그 값을 각 간선의 유량과 역방향 간선의 잔여 용량에 반영한다.
• BFS를 반복하며 더 이상 증가 경로가 없을 때 최대 유량 계산을 종료한다.

So...

이 문제는 네트워크 플로우를 활용해 도시 간 왕복 횟수를 계산하는 문제로, 최대 유량 알고리즘을 효율적으로 설계하는 것이 핵심이었다.