# 그래프 알고리즘

## 그래프 알고리즘이란?

- 그래프
- 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 네트워크 형태의 자료구조
- 다양한 현실 세계의 문제를 모델링하는 데에 사용된다
- 그래프 알고리즘
- 그래프라는 자료구조를 사용하여 문제를 해결하는 알고리즘
- 네트워크, 노드 간의 관계, 경로 등을 다루는 다양한 문제에 적용된다

**그래프 알고리즘은 컴퓨터 과학에서 매우 중요한 주제로, 데이터의 관계를 모델링하고 문제를 해결하는데 광범위하게 사용된다.**

## 그래프 알고리즘의 주요 카테고리

1. **탐색 알고리즘**
- 그래프의 정점을 방문하는 방법을 결정하는 알고리즘
- 대표적인 알고리즘으로는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)이 있다.
2. **최단 경로 알고리즘**
- 두 정점 간의 최단 경로를 찾는 알고리즘
- 대표적인 알고리즘으로는 다익스트라(Dijkstra's) 알고리즘, 벨만-포드(Bellman-Ford) 알고리즘, 플로이드-와샬(Floyd-Warshall) 알고리즘 등이 있다.
3. **사이클 감지 알고리즘**
- 그래프에 사이클이 존재하는지를 찾는 알고리즘
- 대표적인 알고리즘으로 유니온-파인드(Union-Find) 알고리즘 등이 있고, DFS도 자주 사용된다.
4. **위상 정렬**
- 방향성이 있는 비순환 그래프(DAG)의 정점을 순서대로 나열하는 알고리즘
- 보통 종속성이 있는 작업을 순서대로 실행할 때 사용된다.
5. **최소 신장 트리 알고리즘**
- 모든 정점을 포함하면서 간선의 가중치의 합이 최소가 되는 트리를 찾는 알고리즘
- 대표적인 알고리즘으로는 크루스칼(Kruskal's) 알고리즘과 프림(Prim's) 알고리즘 등이 있다
6. **최대 유량 알고리즘**
- 네트워크 플로우에서 특정 소스에서 특정 싱크로 가능한 한 많은 플로우를 보내는 방법을 찾는 알고리즘
- 대표적인 알고리즘으로는 포드-풀커슨(Ford-Fulkerson) 알고리즘과 에드몬드-카프(Edmonds-Karp) 알고리즘 등이 있다.

## 최단 경로 알고리즘


> 집에서 은행으로 가는 가장 빠른 길은?

### 다익스트라(Dijkstra's) 알고리즘

- 가중치가 부여된 방향성 그래프에서 주어진 시작 정점으로부터 다른 모든 정점들까지의 최단 경로를 찾는 알고리즘.
- 다익스트라 알고리즘은 각 단계에서 방문하지 않은 정점 중에서 최단 경로가 가장 짧은 정점을 선택하는 `탐욕적` 접근법과 `동적계획법`을 사용한다.
- 다만, 이 알고리즘은 음수 가중치를 갖는 간선에 대해서는 올바른 결과를 내지 못한다.

#### 다익스트라 알고리즘의 동작 과정

1. 출발 노드를 설정한다.
2. 출발 노드로부터 각 노드까지의 최단 거리를 저장하는 배열을 초기화한다.
3. 출발 노드의 최단 거리를 0으로 설정하고, 나머지 노드들의 최단 거리를 무한대로 초기화한다.
4. 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택한다.
5. 선택한 노드와 연결된 노드들의 최단 거리를 계산하여 최단 거리 배열을 업데이트한다.
6. 모든 노드를 방문할 때까지 4와 5를 반복한다.

<details>
<summary>단계별 확인</summary>
<div markdown="1">










</div>
</details>

### 백준 : 최단경로 문제

- 백준 알고리즘 1753번 ==[링크](https://www.acmicpc.net/problem/1753)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

> 음의 가중치가 없는 그래프에서 최단 경로를 찾는 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다.

#### 최단경로 문제 수도코드 예

1. 노드의 개수 V, 간선의 개수 E, 시작 노드 K를 입력 받는다.
2. 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 생성한다.
3. 최단 거리 테이블을 초기화한다.
4. 우선순위 큐를 생성하여 시작 노드로 가기 위한 최단 경로를 저장한다.
5. 우선순위 큐가 빌 때까지 다음을 반복한다:
   - 가장 최단 거리가 짧은 노드를 꺼낸다.
   - 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
6. 최단 거리 테이블을 출력한다.

#### 최단경로 문제 소스코드 예

import java.util.*;

public class Main {
    // 간선 정보를 저장할 Edge 클래스
    static class Edge implements Comparable<Edge> {
        int to, weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        // 우선순위 큐에서 가중치 기준으로 정렬하기 위한 compareTo 메소드
        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();  // 노드 수
        int E = sc.nextInt();  // 간선 수
        int K = sc.nextInt() - 1; // 시작 노드 (인덱스 0 기준)
        
        // 그래프를 인접 리스트로 표현
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보 입력 받기
        for (int i = 0; i < E; i++) {
            int u = sc.nextInt() - 1; // 출발 노드
            int v = sc.nextInt() - 1; // 도착 노드
            int w = sc.nextInt();    // 가중치
            graph.get(u).add(new Edge(v, w));
        }

        // 최단 거리 배열, 모든 값을 무한대로 초기화
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0; // 시작 노드의 거리는 0으로 초기화
        
        // 우선순위 큐를 사용하여 다음에 방문할 가장 가까운 노드를 결정
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(K, 0));

        // 다익스트라 알고리즘 실행
        while (!pq.isEmpty()) {
            Edge current = pq.poll();

            // 현재 노드를 거쳐 다른 노드로 가는 것이 더 짧지 않은 경우 스킵
            if (dist[current.to] < current.weight) continue;

            for (Edge next : graph.get(current.to)) {
                if (dist[next.to] > dist[current.to] + next.weight) {
                    dist[next.to] = dist[current.to] + next.weight;
                    pq.offer(new Edge(next.to, dist[next.to]));
                }
            }
        }

        // 결과 출력
        for (int i = 0; i < V; i++) {
            if (dist[i] == Integer.MAX_VALUE)
                System.out.println("INF");
            else
                System.out.println(dist[i]);
        }
    }
}

### 벨만-포드(Bellman-Ford) 알고리즘

- 다익스트라 알고리즘과 유사하게, 벨만-포드 알고리즘도 주어진 시작 정점에서 그래프 내의 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다
- 이 알고리즘은 음의 가중치를 가진 간선에 대해서도 올바르게 작동한다
- 벨만-포드 알고리즘은 간선의 relaxation을 그래프의 정점 수 - 1번 반복하여 최단 경로를 찾는다
- relaxation : 두 정점 사이의 최단 거리를 계산하는 과정을 의미한다
- 그러나 이는 **음의 사이클**이 없는 경우에만 올바르게 작동한다

#### 벨만-포드 알고리즘의 동작 과정

1. 출발 노드를 설정한다.
2. 출발 노드로부터 각 노드까지의 최단 거리를 저장하는 배열을 초기화한다.
3. 출발 노드의 최단 거리를 0으로 설정하고, 나머지 노드들의 최단 거리를 무한대로 초기화한다.
4. 모든 간선을 순회하는데, 각 간선을 통해 최단 거리를 갱신할 수 있다면 갱신한다.
5. 4를 전체 노드의 수 - 1번 반복한다. (V-1번 반복)
6. 음의 사이클이 있는지 확인하기 위해 한 번 더 모든 간선을 순회하고 갱신이 발생하면 음의 사이클이 존재한다고 판단한다.

<details>
<summary>단계별 확인</summary>
<div markdown="1">






</div>
</details>

### 플로이드-와샬(Floyd-Warshall) 알고리즘

- 모든 정점 간의 최단 경로를 찾는 알고리즘으로 시작점과 도착점을 모든 가능한 쌍에 대해 계산하는 알고리즘이다
- 동적 프로그래밍 기반의 알고리즘으로, 큰 문제를 작은 부분 문제로 분해하여 문제를 해결한다.
- 플로이드-와샬 알고리즘은 음의 가중치를 가진 간선에 대해서도 올바르게 작동하지만, **음의 사이클**이 있으면 올바른 결과를 내지 못한다.

#### 플로이드-와샬 알고리즘의 동작 과정

1. 모든 노드 간의 거리를 저장하는 2차원 배열을 초기화한다. 자기 자신으로의 거리는 0, 직접적인 간선이 없는 노드들 간의 거리는 무한대로 초기화한다.
2. 노드 i에서 노드 j로 가는 직접적인 간선이 있다면, 그 거리를 배열에 저장한다.
3. 세 노드 i, j, k에 대해, i에서 j로 가는 거리가 i에서 k를 거쳐 j로 가는 거리보다 크다면, i에서 j로 가는 거리를 갱신한다. (i에서 k를 거쳐 j로 가는 거리로)
4. 3의 과정을 모든 노드 쌍 (i, j)에 대해 반복한다.

<details>
<summary>단계별 확인</summary>
<div markdown="1">







</div>
</details>

> 참고 : https://visualgo.net/en/sssp

### 백준 : 경로 찾기 문제

- 백준 알고리즘 11403번 ==[링크](https://www.acmicpc.net/problem/11403)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

> 해당 문제는 모든 정점에서 모든 정점으로의 최단 경로를 구해야 하기 때문에 플로이드-와샬 알고리즘을 이용하여 해결할 수 있다.

#### 경로 찾기 문제 수도코드 예

1. 정점의 개수 N을 입력 받는다.
2. 인접 행렬을 입력 받는다.
3. 플로이드-와샬 알고리즘을 적용하여 모든 정점에서 모든 정점으로의 최단 경로를 구한다.
4. 결과를 출력한다.

#### 경로 찾기 문제 소스코드 예

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] graph = new int[n][n];

        // 그래프 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        // 플로이드-와샬 알고리즘 적용
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][k] == 1 && graph[k][j] == 1) {
                        graph[i][j] = 1;
                    }
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(graph[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.print(sb.toString());
    }
}

## 사이클 감지 알고리즘

- 그래프 내에서 사이클(즉, 어떤 노드에서 시작해서 그 노드로 돌아오는 경로)이 존재하는지를 찾는 알고리즘
- 사이클 감지 알고리즘으로 대표적인 알고리즘에는 깊이 우선 탐색(DFS)과 유니온-파인드 알고리즘이 있다

### 깊이 우선 탐색(DFS)를 이용한 사이클 감지

- DFS는 현재 노드에서 방문하지 않은 이웃 노드를 하나씩 방문하면서 사이클을 찾는다.
- 만약 DFS가 진행되는 도중에 이미 방문한 노드를 다시 방문하게 된다면, 그래프에는 사이클이 존재한다고 판단할 수 있다.

### 유니온-파인드(Union-Find) 알고리즘을 이용한 사이클 감지

#### 유니온 파인드란?

- '합집합 찾기' 알고리즘
- 서로소 집합(Disjoint-Set)알고리즘 이라고도 부른다

#### 유니온 파인드의 과정

- **유니온(Union) 과정:** 유니온이란 '합집합'을 의미한다. 두 개의 서로 다른 집합을 선택하여, 두 집합을 하나로 합치는 과정을 말한다. 유니온 연산을 통해 서로 다른 집합에 속해 있는 두 원소가 같은 집합에 속하게 된다.
- **파인드(Find) 과정:** 파인드란 '찾기'를 의미한다. 어떤 원소가 어떤 집합에 속해 있는지 찾는 과정을 말한다. 즉, 각 원소에 대해 어떤 집합에 속해 있는지를 찾아내는 연산이다.
> **Union-Find** > 
- **Path compression 과정:** 유니온-파인드 알고리즘의 효율성을 크게 높이는 테크닉. 파인드 연산을 수행하며 거치는 모든 노드들을 집합의 루트에 직접 연결하는 것. 이렇게 하면 트리의 높이를 대폭 줄일 수 있으므로, 이후에 같은 노드에 대한 파인드 연산이 발생할 때의 시간 복잡도를 크게 줄일 수 있다.
> **Path compression** > 

### 백준 : 집합의 표현 문제

- 백준 알고리즘 1717번 ==[링크](https://www.acmicpc.net/problem/1717)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

> 집합을 표현하고, 집합을 합치거나(union), 어떤 집합에 포함되어 있는지 확인(find)하는 연산을 빠르게 수행하기 위해 유니온 파인드를 사용할 수 있다.

#### 집합의 표현 문제 수도코드 예

1. n, m을 입력 받는다.
2. n개의 원소를 각각의 집합으로 표현하기 위해 부모 테이블을 초기화한다.
3. m개의 연산을 수행하며, 각 연산에 따라 유니온 파인드 연산을 수행한다.
4. 연산 결과를 출력한다.

#### 집합의 표현 문제 소스코드 예

import java.io.IOException;
import java.util.Scanner;

public class Main {
    static int[] parent; // 각 원소의 부모 노드를 저장하는 배열

    // x가 속한 집합의 루트 노드를 찾는 함수
    public static int find(int x) {
        if (parent[x] == x) {
            return x; // x가 루트 노드이면 x를 반환
        }
        return parent[x] = find(parent[x]); // 경로 압축을 적용하면서 재귀적으로 루트 노드를 찾음
    }

    // x와 y가 속한 집합을 합치는 함수
    public static void union(int x, int y) {
        x = find(x); // x의 루트 노드를 찾음
        y = find(y); // y의 루트 노드를 찾음

        if (x != y) {
            parent[y] = x; // y의 루트 노드의 부모를 x의 루트 노드로 설정하여 두 집합을 합침
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt(); // 총 원소의 수
        int m = sc.nextInt(); // 수행할 연산의 수

        parent = new int[n + 1]; // 원소의 개수만큼 부모 배열을 초기화
        for (int i = 0; i <= n; i++) {
            parent[i] = i; // 초기에 각 원소의 부모는 자기 자신
        }

        StringBuilder sb = new StringBuilder(); // 결과를 저장할 StringBuilder
        for (int i = 0; i < m; i++) {
            int command = sc.nextInt(); // 연산의 종류 (0: 합집합, 1: 같은 집합인지 확인)
            int a = sc.nextInt(); // 연산에 사용될 원소 a
            int b = sc.nextInt(); // 연산에 사용될 원소 b

            if (command == 0) {
                union(a, b); // a와 b의 집합을 합침
            } else if (command == 1) {
                if (find(a) == find(b)) {
                    sb.append("YES\n"); // a와 b가 같은 집합에 속하면 "YES"
                } else {
                    sb.append("NO\n"); // a와 b가 다른 집합에 속하면 "NO"
                }
            }
        }
        System.out.print(sb); // 결과 출력
    }
}

## 위상 정렬(Topology Sort) 알고리즘


- '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘
- 싸이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에 대해서만 수행될 수 있다
- 그래프에 싸이클이 있다면, 싸이클에 포함된 노드 중 어떤 노드도 진입 차수가 0이 되지 않아 결과를 만들 수 없기 때문

### 위상 정렬 알고리즘의 동작 과정

1. 모든 노드에 대해 들어오는 간선의 수(진입 차수)를 계산한다.
2. 진입 차수가 0인 모든 노드를 큐에 넣는다.
3. 다음 과정을 큐가 빌 때까지 반복한다:
   - 큐에서 노드를 꺼내 그 노드를 출력하거나 리스트에 추가한다.
   - 해당 노드에서 나가는 모든 간선을 그래프에서 제거한다.
   - 이 때, 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다.

### 백준 : 문제집 문제

- 백준 알고리즘 1766번 ==[링크](https://www.acmicpc.net/problem/1766)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

> 선행 작업이 있는 문제들을 풀기 위해서는 위상 정렬 알고리즘을 사용할 수 있다.

#### 문제집 문제 수도코드 예

1. 문제의 수 N, 정보의 수 M을 입력 받는다.
2. 각 문제의 선행 문제 정보를 저장하기 위한 인접 리스트를 초기화한다.
3. 각 문제의 진입 차수를 저장하기 위한 배열을 초기화한다.
4. 선행 문제 정보를 입력 받으며, 인접 리스트와 진입 차수를 갱신한다.
5. 우선순위 큐를 생성하여 진입 차수가 0인 노드를 삽입한다.
6. 우선순위 큐가 빌 때까지 다음을 반복한다:
   - 진입 차수가 0인 노드를 꺼낸다.
   - 해당 노드를 풀고, 진입 차수를 갱신한다.
7. 결과를 출력한다.

#### 문제집 문제 소스코드 예

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 문제의 수
        int M = sc.nextInt(); // 정보의 수
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        int[] indegree = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            adj.get(A).add(B);
            indegree[B]++;
        }

        // 우선순위 큐를 사용하여 문제 번호가 작은 것을 우선적으로 푸는 것을 구현
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 진입 차수가 0인 노드를 우선순위 큐에 삽입
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                pq.offer(i);
            }
        }

        // 결과를 저장할 리스트
        ArrayList<Integer> result = new ArrayList<>();

        while (!pq.isEmpty()) {
            int current = pq.poll();
            result.add(current);

            for (int next : adj.get(current)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    pq.offer(next);
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int num : result) {
            sb.append(num).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

## 최소 신장 트리 (Minimum Spanning Tree, MST)

### 신장 트리(Spanning Tree)란?

- 신장트리는 연결 그래프의 부분 그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리로 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다
- 단 그래프에 사이클이 형성이 되면 안된다
- 신장트리는 연결 그래프일 때 깊이 우선 탐색이나 너비 우선 탐색 방을 통하여 구현이 가능하다
- 이때 주어진 연결 그래프에 대한 신장트리는 하나가 아니라 다양할 수 있다


### 최소 신장 트리(Minimum Spanning Tree, MST)란?

- 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리
- 그래프의 모든 노드를 포함하면서 간선의 가중치 합이 최소가 되는 트리
- 최소 신장 트리를 구하는 대표적인 두 알고리즘으로는 크루스칼(Kruskal's) 알고리즘과 프림(Prim's) 알고리즘이 있다

### 크루스칼(Kruskal's) 알고리즘

- 탐욕적 기법을 사용하여 최소 신장 트리를 구하는 알고리즘
- 그래프의 간선들을 가중치의 오름차순으로 선택하면서 사이클을 형성하지 않는 최소 신장 트리를 구하는 방법

#### 크루스칼 알고리즘의 동작 과정

1. 그래프의 모든 간선들을 오름차순으로 정렬한다.
2. 빈 집합인 신장 트리를 초기화한다.
3. 각 노드를 독립적인 집합으로 만든다. (Union-Find 사용)
4. 정렬된 간선 목록을 순회하면서 다음을 반복한다:
   - 현재 간선을 검토한다.
   - 현재 간선의 두 노드가 서로 다른 집합에 속해 있다면:
     - 현재 간선을 신장 트리에 추가한다.
     - 두 노드가 속한 집합을 합친다. (Union-Find 사용)
   - 두 노드가 같은 집합에 속해 있다면 현재 간선은 사이클을 형성하므로 버린다.
5. 신장 트리를 반환한다.

<details>
<summary>단계별 확인</summary>
<div markdown="1">


</div>
</details>

### 프림(Prim's) 알고리즘

- 탐욕적 기법을 사용하여 최소 신장 트리를 구하는 알고리즘
- 임의의 출발 노드부터 시작하여 현재 트리에 연결된 간선들 중 가장 작은 가중치를 가진 노드와 연결되는 간선을 선택하여 최소 신장 트리를 구하는 방법

#### 프림 알고리즘의 동작 과정

1. 임의의 노드를 선택하여 시작한다. 이 노드를 신장 트리에 추가한다.
2. 신장 트리에 연결된 노드들을 확인하여, 신장 트리에 아직 추가되지 않은 노드 중 가장 가중치가 낮은 간선을 선택한다.
3. 선택한 간선에 연결된 노드를 신장 트리에 추가합니다. 이때 선택한 간선도 신장 트리에 추가한다.
4. 모든 노드가 신장 트리에 포함될 때까지 2번과 3번 과정을 반복한다.
5. 최종적으로 만들어진 신장 트리를 반환한다. 이 결과는 그래프의 모든 노드를 포함하고, 가중치의 합이 최소인 트리를 형성하게 된다

<details>
<summary>단계별 확인</summary>
<div markdown="1">


</div>
</details>

> 참고 : https://visualgo.net/en/mst

### 백준 : 최소 스패닝 트리 문제

- 백준 알고리즘 1197번 ==[링크](https://www.acmicpc.net/problem/1197)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

> 최소 스패닝 트리를 찾기 위해서는 크루스칼 알고리즘이나 프림 알고리즘을 사용할 수 있다. 여기서는 크루스칼 알고리즘을 사용해본다.

#### 최소 스패닝 트리 문제 수도코드 예

1. 정점의 개수 V, 간선의 개수 E를 입력 받는다.
2. 간선 정보를 입력 받으며, 간선 정보를 가중치를 기준으로 오름차순 정렬한다.
3. 각 정점을 개별 집합으로 만들고, 모든 간선을 확인하며 사이클이 발생하지 않는 경우에만 최소 스패닝 트리에 포함시킨다.
4. 최소 스패닝 트리에 포함된 간선의 가중치 합을 출력한다.

#### 최소 스패닝 트리 문제 소스코드 예

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

public class Main {
    static int[] parent;  // 각 정점의 부모를 저장할 배열

    // 유니온 파인드의 '파인드' 함수: x가 속한 집합의 루트를 찾는다
    static int find(int x) {
        if (parent[x] == x) return x;  // 루트 노드인 경우 자기 자신을 반환
        return parent[x] = find(parent[x]);  // 경로 압축을 통해 집합의 루트를 찾음
    }

    // 유니온 파인드의 '유니온' 함수: x와 y의 집합을 합친다
    static void union(int x, int y) {
        x = find(x);  // x의 루트 노드 찾기
        y = find(y);  // y의 루트 노드 찾기
        if (x != y) {
            parent[y] = x;  // y의 루트 노드의 부모를 x의 루트 노드로 설정하여 두 집합을 합침
        }
    }

    // 간선 클래스, Comparable 인터페이스를 구현하여 간선을 가중치에 따라 정렬 가능
    static class Edge implements Comparable<Edge> {
        int start, end, weight;  // 간선의 시작점, 끝점, 가중치

        Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        // 가중치를 기준으로 오름차순 정렬하는 compareTo 메서드 구현
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

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

        int V = sc.nextInt();  // 정점의 개수 입력 받음
        int E = sc.nextInt();  // 간선의 개수 입력 받음
        parent = new int[V + 1];  // 정점 인덱스를 1부터 사용하기 위해 V+1 크기로 배열 초기화
        for (int i = 1; i <= V; i++) parent[i] = i;  // 모든 정점의 초기 부모를 자기 자신으로 설정

        List<Edge> edges = new ArrayList<>();  // 모든 간선을 저장할 리스트
        for (int i = 0; i < E; i++) {
            int u = sc.nextInt();  // 간선의 시작점
            int v = sc.nextInt();  // 간선의 끝점
            int w = sc.nextInt();  // 간선의 가중치
            edges.add(new Edge(u, v, w));  // 간선 리스트에 간선 추가
        }

        Collections.sort(edges);  // 모든 간선을 가중치 기준으로 오름차순 정렬

        int result = 0;  // 최소 스패닝 트리의 가중치 합을 저장할 변수
        for (Edge e : edges) {
            if (find(e.start) != find(e.end)) {  // 두 정점이 서로 다른 집합에 속해 있는 경우 (사이클이 발생하지 않을 경우)
                union(e.start, e.end);  // 두 정점을 연결 (유니온)
                result += e.weight;  // 가중치 합에 추가
            }
        }

        System.out.println(result);  // 최소 스패닝 트리의 가중치 합 출력
    }
}

## 네트워크 플로우(Network Flow), 최대 유량 알고리즘(Max Flow Algorithm)

- 네트워크 플로우 알고리즘은 네트워크 상에서 소스(source)에서 싱크(sink)로 흐르는 최대 흐름의 크기를 찾는 알고리즘이다.
- 네트워크 플로우는 각 간선에 흐르는 흐름의 양을 나타내는 유량(flow)을 사용하여 네트워크의 최적화 문제를 해결한다.
- 일반적으로 그래프 내에서 `유량/용량`이라는 개념을 사용하여 각 간선에 흐를 수 있는 최대 유량을 정의한다.

- 최대 유량 알고리즘(Max Flow Algorithm)은 이러한 플로우 네트워크에서 소스 노드에서 싱크 노드로 흘러갈 수 있는 플로우의 최대량을 찾는 알고리즘이다
- 최대 유량 알고리즘은 다양한 종류가 있지만, 가장 널리 알려진 것은 포드-풀커슨(Ford-Fulkerson) 알고리즘과 에드몬드-카프(Edmonds-Karp) 알고리즘이 있다
- 기본적으로 두 알고리즘은 부르트포스의 특징을 가진다

### 포드-풀커슨 알고리즘 (Ford-Fulkerson Algorithm)

- **DFS**를 이용한 알고리즘

1. 네트워크에 존재하는 모든 간선의 유량을 0 으로 초기화하고, 역방향 간선의 유량도 0 으로 초기화한다.
2. 소스에서 싱크로 갈 수 있는, 잔여 용량이 남은 경로를 DFS 로 탐색한다.
3. 해당 경로에 존재하는 간선들의 잔여 용량 중, 가장 작은 값을 유량으로 흘려보낸다.
4. 해당 유량에 음수값을 취해, 역방향 간선에도 흘려보낸다. (유량 상쇄)
5. 더 이상 잔여 용량이 남은 경로가 존재하지 않을때까지 반복한다.

### 에드몬드-카프 알고리즘 (Edmonds-Karp Algorithm)

- **BFS**를 이용한 알고리즘

1. 네트워크에 존재하는 모든 간선의 유량을 0 으로 초기화하고, 역방향 간선의 유량도 0 으로 초기화한다.
2. 소스에서 싱크로 갈 수 있는, 잔여 용량이 남은 경로를 BFS 로 탐색한다.
3. 해당 경로에 존재하는 간선들의 잔여 용량 중, 가장 작은 값을 유량으로 흘려보낸다.
4. 해당 유량에 음수값을 취해, 역방향 간선에도 흘려보낸다. (유량 상쇄)
5. 더 이상 잔여 용량이 남은 경로가 존재하지 않을때까지 반복한다.

> 포드-폴커슨과 에드몬드-카프 알고리즘과의 차이점이라면, **경로 탐색**을 위해 **DFS**를 사용하는지 **BFS**를 사용하는지의 차이이다.

역방향 간선은 역방향으로의 플로우를 가능하게 하며, 이는 원래의 간선에서 플로우를 '취소'하는 데 사용될 수 있다.

예를 들어, 노드 A에서 노드 B로 10의 플로우를 보냈다고 가정해 보자. 나중에 더 나은 최대 플로우 솔루션을 찾기 위해 이 플로우를 줄이고 싶을 수 있다. 이 경우, B에서 A로 플로우를 보내는 것은 기본적으로 A에서 B로 보낸 플로우를 줄이는 것과 같다. 그래서 역방향 간선이 필요하며 이렇게 하면 플로우의 양을 조정하면서 최적의 솔루션을 찾을 수 있다.

<details>
<summary>단계별 확인</summary>
<div markdown="1">

| 이미지 | 설명 |
|---|---|
|| S에서 T로 가는 최대유량 그래프 |
|| S에서 T로 가는 증가경로를 찾는다 |
|| 찾아낸 경로에 보낼수 있는 최대 유량을 찾는다 |
|| 최대유량만큼 흘러보낸다 |
|| 경로를 찾고, 최대유량을 흘려보내는걸 반복한다. |
|| 경로를 찾고, 최대유량을 흘려보내는걸 반복한다. 이제 더 이상 이 방식으로는 경로를 찾을 수 없다. |
|| 하지만, 아직 추가로 유량을 더 보낼 수 있는 경로가 있다. |
|| 추가적인 경로를 찾기 위해 역간선이 있다고 가정한다. |
|| 역간선을 이용하여 다음과 같은 추가적인 경로를 찾을 수 있다. |
|| 경로의 유량/용량 표는 이와 같이 표현될 수 있다. |
|| 역간선을 표현함으로써 추가로 경로를 찾을 수 있고, 이 경로로 추가로 유량을 보낼 수 있다. |
|| 최종 결과는 다음과 같다. |

</div>
</details>

> 참고 : https://visualgo.net/en/maxflow

### 백준 : 도시 왕복하기 1 문제

- 백준 알고리즘 17412번 ==[링크](https://www.acmicpc.net/problem/17412)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 도시 왕복하기 1 문제 수도코드 예

1. 도시의 수 N, 도로의 수 P를 입력 받는다.
2. 인접 리스트를 초기화하고, 용량 행렬과 유량 행렬을 초기화한다.
3. 도로의 정보를 입력 받으며, 인접 리스트와 용량 행렬을 갱신한다.
4. 최대 유량을 찾기 위해 maxFlow 함수를 호출한다.
   - 소스에서 싱크로의 최대 유량을 찾는다.
   - 경로가 존재하지 않을 때까지 유량을 흘려보낸다.
   - 경로를 찾을 때마다 유량을 갱신하고, 역방향 간선도 갱신한다.
   - 최대 유량을 찾을 때까지 반복한다.
5. 최대 유량을 출력한다.

#### 도시 왕복하기 1 문제 소스코드 예

import java.util.*;

public class Main {
    static int N, P;  // 도시의 수와 도로의 수
    static ArrayList<Integer>[] graph; // 인접 리스트
    static int[][] capacity; // 용량 행렬
    static int[][] flow; // 유량 행렬

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

        N = sc.nextInt();  // 도시의 수
        P = sc.nextInt();  // 도로의 수

        graph = new ArrayList[N + 1];
        capacity = new int[N + 1][N + 1];
        flow = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < P; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            graph[a].add(b);
            graph[b].add(a);  // 역방향 간선도 추가
            capacity[a][b] += 1;  // 동일한 방향으로 여러 도로가 있을 수 있음
        }

        System.out.println(maxFlow(1, 2));  // 1번 도시에서 2번 도시로의 최대 유량 계산
        sc.close();
    }

    static int maxFlow(int source, int sink) {
        int totalFlow = 0;  // 총 유량

        while (true) {
            int[] parent = new int[N + 1];  // 경로 복원을 위한 배열
            Arrays.fill(parent, -1);
            Queue<Integer> queue = new LinkedList<>();
            parent[source] = source;  // 소스는 소스로 초기화
            queue.add(source);

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

                for (int next : graph[current]) {
                    // 유량이 남아있고 아직 방문하지 않은 노드라면
                    if (capacity[current][next] - flow[current][next] > 0 && parent[next] == -1) {
                        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;
    }
}