## 과제 : 백준 문제 풀이

목표 : 백준 문제를 풀어본다.

- [상근이의 여행](https://www.acmicpc.net/problem/9372)
- [최대 유량](https://www.acmicpc.net/problem/6086)

---

## 과제 : 백준 문제 풀이 모범답안

### 상근이의 여행

import java.io.*;
import java.util.*;

public class Main {
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static boolean union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            parent[y] = x;
            return true;
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            int N = scanner.nextInt();
            int M = scanner.nextInt();
            parent = new int[N + 1];
            for (int i = 1; i <= N; i++) parent[i] = i;

            int edgeCount = 0;
            for (int i = 0; i < M; i++) {
                int u = scanner.nextInt();
                int v = scanner.nextInt();

                if (union(u, v)) {
                    edgeCount++;
                }
            }
            sb.append(edgeCount).append("\n");
        }

        System.out.print(sb.toString());
        scanner.close();
    }
}

해당 문제는 위처럼 최소 신장 트리로 해결할 수도 있지만, 더 간단한 방법으로 해결할 수 있다.

최소 신장 트리는 노드의 수 - 1개의 간선으로 구성되어 있기 때문에, 모든 국가가 연결되어 있다면 간선의 수는 N - 1이 된다.

여기서는 간선의 수를 구하는 것이 목적이므로, 간선의 수만 구하면 된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();  // 테스트 케이스의 수

        for (int i = 0; i < T; i++) {
            int N = sc.nextInt();  // 국가의 수
            int M = sc.nextInt();  // 비행기의 종류

            // 비행 경로 입력 받기 (실제로 경로를 저장할 필요는 없음)
            for (int j = 0; j < M; j++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
            }

            // 국가의 수 - 1 출력 (최소 신장 트리의 간선 수)
            System.out.println(N - 1);
        }
    }
}

### 최대 유량

import java.io.*;
import java.util.*;

public class Main {
    static final int MAX = 52; // 알파벳 대소문자 총 개수 (대문자 26개, 소문자 26개)
    static int[][] capacity; // 각 간선에 대한 용량을 저장할 2차원 배열
    static int[][] flow; // 실제 흐르는 유량을 저장할 2차원 배열
    static List<Integer>[] graph; // 그래프의 인접 리스트

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine()); // 간선의 개수 입력 받음

        capacity = new int[MAX][MAX];
        flow = new int[MAX][MAX];
        graph = new ArrayList[MAX];
        for (int i = 0; i < MAX; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            String line = sc.nextLine();
            String[] input = line.split(" ");
            int u = parse(input[0].charAt(0)); // 출발 정점
            int v = parse(input[1].charAt(0)); // 도착 정점
            int cap = Integer.parseInt(input[2]); // 용량

            capacity[u][v] += cap; // 중복 간선 처리를 위해 용량을 누적
            capacity[v][u] += cap; // 역방향 간선의 용량도 누적
            graph[u].add(v);
            graph[v].add(u);
        }

        // 최대 유량을 계산하고 출력
        System.out.println(maxFlow(parse('A'), parse('Z')));
    }

    // 에드몬드-카프 알고리즘을 구현한 함수
    static int maxFlow(int source, int sink) {
        int totalFlow = 0;

        while (true) {
            int[] parent = new int[MAX]; // 증가 경로를 찾기 위한 부모 노드 저장 배열
            Arrays.fill(parent, -1);
            Queue<Integer> queue = new LinkedList<>();
            queue.add(source);

            while (!queue.isEmpty() && parent[sink] == -1) {
                int current = queue.poll();

                for (int next : graph[current]) {
                    // 아직 방문하지 않았고, 남은 용량이 있는 경우
                    if (parent[next] == -1 && capacity[current][next] - flow[current][next] > 0) {
                        queue.add(next);
                        parent[next] = current; // 경로를 구성
                        if (next == sink) break; // 도착지에 도달한 경우 루프 종료
                    }
                }
            }

            if (parent[sink] == -1) break; // 더 이상 증가 경로를 찾을 수 없는 경우

            int amount = Integer.MAX_VALUE;
            // 증가 경로에 따라 가능한 최대 유량을 찾음
            for (int p = sink; p != source; p = parent[p]) {
                amount = Math.min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
            }

            // 증가 경로에 유량을 추가
            for (int p = sink; p != source; p = parent[p]) {
                flow[parent[p]][p] += amount;
                flow[p][parent[p]] -= amount;
            }

            totalFlow += amount; // 전체 유량에 추가
        }

        return totalFlow; // 계산된 최대 유량 반환
    }

    // 문자를 정수로 매핑하는 함수
    static int parse(char c) {
        if (c <= 'Z') return c - 'A';
        return c - 'a' + 26; // 소문자인 경우
    }
}