[Gold III] 최대 유량 - 6086

문제 링크

성능 요약

메모리: 35004 KB, 시간: 60 ms

분류

구현, 그래프 이론, 시뮬레이션, 최대 유량

문제 설명

농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다.

두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다.

  +---5---+---3---+    ->    +---3---+

게다가, 병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다.

    +---5---+
 ---+       +---    ->    +---8---+
    +---3---+

마지막으로, 어떤 것에도 연결돼 있지 않은 파이프는 물을 흐르게 하지 못하므로 제거된다.

    +---5---+
 ---+               ->    +---3---+
    +---3---+--

이로 인해 복잡하게 연결된 모든 배수관들은 한개의 최대 유량을 갖는 배수관으로 만들어진다.

주어진 파이프들의 맵으로부터 우물(A)와 외양간(Z) 사이의 유량을 결정하라.

각 노드의 이름은 알파벳으로 지어져 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +---3---+---5---+---4---+
                         C       D

파이프 BC와 CD는 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

그러면 BD와 DZ 역시 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

병렬 연결된 BZ 역시 합쳐진다.

                 B
        A+---3---+---9---+Z

그러면 AB와 BZ 역시 합쳐질 수 있고 용량 3인 배수관 하나가 만들어진다.

        A+---3---+Z

한 파이프들의 집합을 읽고. 두개의 끝점을 가진 파이프로 만들어놓은 뒤 A부터 Z까지 흐르는 최대 유량을 계산하라. 모든 파이프들은 위의 규칙을 적용시켜 줄일 수 있다.

i번째 파이프는 두개의 다른 노드 a_i와 b_i와 연결돼 있고 F_i (1 ≤ F_i ≤ 1,000)만큼의 유량을 갖는다. 알파벳은 같지만, 대소문자가 다르면 다른 문자이다. 파이프는 양방향으로 흐를 수 있다.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위치에 파이프의 용량이 주어진다.

출력

첫째 줄에 A에서 Z까지의 최대 유량을 출력한다.

---

문제 풀이

문제 분석

이 문제는 농장에서 우물(A)과 외양간(Z)을 잇는 배수관 네트워크에서 'A'에서 'Z'까지 보낼 수 있는 최대 물의 양, 즉 최대 유량을 구하는 문제입니다.

• 입력:
  • 첫째 줄에 파이프의 개수 N (1 ≤ N ≤ 700)이 주어집니다.
  • 이후 N줄에 걸쳐 각 파이프의 정보가 주어집니다. 정보는 두 노드의 이름(알파벳 대문자 또는 소문자)과 해당 파이프의 용량(1 ≤ F ≤ 1,000)으로 구성됩니다.
  • 노드 이름은 알파벳으로 주어지며, 'A'부터 'Z'까지 대문자 26개와 'a'부터 'z'까지 소문자 26개, 총 52개의 노드가 가능합니다. 대소문자가 다르면 다른 노드입니다.
  • 파이프는 양방향으로 물이 흐를 수 있습니다.
• 출력: 'A'에서 'Z'까지 보낼 수 있는 최대 유량을 정수 형태로 출력합니다.
• 핵심: 문제에 설명된 "두 관의 유량 중 최솟값으로 흐르게 된다", "병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다" 등의 내용은 표준적인 최대 유량 문제의 성질을 설명하는 것이며, 별도로 구현할 필요 없이 일반적인 최대 유량 알고리즘으로 해결할 수 있습니다.

접근 방법

이 문제는 전형적인 최대 유량 (Maximum Flow) 문제입니다. 최대 유량 문제는 어떤 네트워크(그래프)에서 출발지(소스, Source)에서 도착지(싱크, Sink)까지 보낼 수 있는 최대의 유량을 찾는 문제입니다.

이 문제에서는 에드몬드-카프(Edmonds-Karp) 알고리즘을 사용하여 해결합니다.

• 에드몬드-카프 알고리즘 선택 이유:
  1. 개념적 단순성: 잔여 그래프(Residual Graph)에서 BFS(너비 우선 탐색)를 사용하여 소스에서 싱크까지의 경로(증가 경로, Augmenting Path)를 찾고, 해당 경로의 병목 용량(가장 작은 잔여 용량)만큼 유량을 흘려보내는 과정을 반복합니다.
  2. 구현의 용이성: BFS를 기반으로 하기 때문에 구현이 비교적 쉽습니다.
  3. 작은 노드 수: 이 문제의 노드 수는 최대 52개로 매우 작습니다. 에드몬드-카프 알고리즘은 노드 수가 적은 경우에 효율적으로 작동합니다. (V: 노드 수, E: 엣지 수 일 때, 시간 복잡도는 일반적으로 $O(V \cdot E^2)$ 이며, 여기서는 인접 행렬을 사용하므로 $O(V^3 \cdot N)$ 정도로 볼 수 있습니다. $V=52$ 이면 충분히 빠릅니다.)

구현 설명

주어진 코드는 에드몬드-카프 알고리즘을 사용하여 최대 유량을 계산합니다.

1. 노드 매핑 및 그래프 초기화

• 노드 매핑 함수 (mapping): 알파벳 문자를 정수 인덱스로 변환하는 함수입니다.
  • 'A'부터 'Z'까지는 0부터 25로 매핑합니다 (ord(c) - ord('A')).
  • 'a'부터 'z'까지는 26부터 51로 매핑합니다 (ord(c) - ord('a') + 26).
  • 이렇게 함으로써 총 52개의 노드를 0부터 51까지의 정수 인덱스로 다룰 수 있게 됩니다.
• 그래프 표현: board와 line이라는 두 개의 52x52 크기의 2차원 배열(인접 행렬)을 사용합니다.
  • board[u][v]: 노드 u에서 v로 가는 파이프의 원래 용량을 저장합니다.
  • line[u][v]: 노드 u에서 v로 가는 파이프에 현재 흐르는 유량을 저장합니다.
• 입력 처리: N개의 파이프 정보를 읽어 board를 초기화합니다.
  • 파이프는 양방향이므로, u와 v 사이에 용량 w의 파이프가 있다면 board[u][v]와 board[v][u] 모두에 w를 더합니다. (만약 두 노드 사이에 여러 파이프가 있다면 용량이 합산됩니다.)

2. 증가 경로 찾기 (BFS)

• BFS 함수 (BFS(start, end, parent)): 소스(start)에서 싱크(end)까지 유량을 보낼 수 있는 경로를 찾습니다.
  • visited 배열은 현재 BFS 탐색에서 방문한 노드를 표시하여 중복 방문 및 무한 루프를 방지합니다.
  • q는 BFS를 위한 큐입니다.
  • parent 배열은 경로를 역추적하기 위해 각 노드의 직전 노드를 저장합니다.
  • 잔여 용량 확인: board[x][i] - line[x][i] > 0 조건이 핵심입니다. 이는 x에서 i로 갈 수 있는 잔여 용량이 남아있는지를 확인합니다. (즉, x에서 i로 아직 더 유량을 보낼 수 있는지). 잔여 용량이 있는 경우에만 경로 탐색을 계속합니다.
  • 경로를 찾으면 True를 반환하고, 찾지 못하면 False를 반환합니다.

3. 유량 증가 및 잔여 용량 갱신

• 메인 루프: BFS(start, end, parent)가 True를 반환하는 동안(즉, 증가 경로를 계속 찾을 수 있는 동안) 반복합니다.
  • 병목 용량 (a) 계산: 찾은 경로를 end에서 start로 역추적하면서 해당 경로의 모든 간선에서 board[u][v] - line[u][v] (잔여 용량) 중 최솟값을 찾아 a에 저장합니다. 이 a가 현재 경로를 통해 흘려보낼 수 있는 최대 유량입니다.
  • 유량 갱신: 다시 경로를 역추적하면서 각 간선 u -> v에 대해:
    • line[u][v] += a: 정방향 간선 u -> v에 a만큼 유량을 추가합니다.
    • line[v][u] -= a: 역방향 간선 v -> u에 a만큼 유량을 감소시킵니다. 이는 역방향 간선의 잔여 용량을 a만큼 늘리는 효과가 있으며, 나중에 v에서 u로 유량을 "되돌려 보낼" 수 있게 하여 더 효율적인 경로를 찾을 기회를 제공합니다.
  • 총 유량 합산: answer에 a를 더하여 전체 최대 유량을 누적합니다.
• BFS가 더 이상 경로를 찾지 못하면 루프를 종료하고 answer를 출력합니다.

⏱복잡도 분석

• 노드 수 (V): 'A''Z' (26개) + 'a''z' (26개) = 52개.

• 엣지 수 (E): 최대 N개의 파이프가 주어지지만, 인접 행렬을 사용하므로 각 BFS에서 이웃을 찾는 데 O(V) 시간이 걸립니다.

• 시간 복잡도:

  • 에드몬드-카프 알고리즘의 시간 복잡도는 일반적으로 $O(V \cdot E^2)$ 또는 $O(F_{max} \cdot E)$ (여기서 $F_{max}$는 최대 유량)로 알려져 있습니다.
  • 이 코드에서는 인접 행렬을 사용하며, BFS를 한 번 수행하는 데 $O(V^2)$ 시간이 걸립니다. (각 노드에서 모든 다른 노드를 확인).
  • 최대 유량이 증가하는 횟수(증가 경로를 찾는 횟수)는 일반적으로 $O(V \cdot E)$번입니다. (혹은 $F_{max}$번)
  • 따라서 전체 시간 복잡도는 $O(\text{경로 탐색 횟수} \times \text{경로 탐색 시간}) = O((V \cdot E) \times V^2) = O(V^3 \cdot E)$가 됩니다.
  • 이 문제에서 $V=52$이고 $E$는 실제 간선 수보다는 N에 비례하는 값으로 볼 수 있습니다 (최대 N=700).
  • $52^3 \times 700 \approx 140608 \times 700 \approx 9.8 \times 10^7$ 연산으로 추정됩니다. 이 정도 연산량은 Python의 경우 60ms의 시간 제한 내에 충분히 실행될 수 있습니다.

• 공간 복잡도:

  • board: $O(V^2)$ (52x52 정수형 배열)
  • line: $O(V^2)$ (52x52 정수형 배열)
  • visited: $O(V)$ (52개 불리언 배열)
  • parent: $O(V)$ (52개 정수형 배열)
  • deque (큐): 최악의 경우 $O(V)$
  • 총 공간 복잡도는 $O(V^2)$ 입니다. $52^2 = 2704$는 매우 작은 메모리 사용량입니다.

핵심 포인트

1. 노드 매핑: 알파벳 문자로 주어진 노드들을 배열 인덱스로 사용하기 위해 'A'-'Z'는 0-25, 'a'-'z'는 26-51로 매핑하는 것이 중요합니다. 이는 고정된 크기의 인접 행렬을 사용할 수 있게 합니다.
2. 잔여 그래프와 역방향 간선: 에드몬드-카프 알고리즘의 핵심은 잔여 용량을 계산하고 관리하는 것입니다. board[u][v] - line[u][v]로 현재 잔여 용량을 확인하며, 유량을 보낼 때 정방향 간선(line[u][v] += a)과 함께 역방향 간선(line[v][u] -= a)의 유량을 갱신하여 나중에 유량을 "되돌려 보낼" 수 있는 유연성을 확보하는 것이 중요합니다.
3. BFS를 이용한 증가 경로 탐색: 소스에서 싱크까지 잔여 용량이 남아있는 경로를 BFS를 통해 효율적으로 찾아냅니다. BFS는 가장 짧은 경로를 찾아주며, 이는 에드몬드-카프 알고리즘의 효율성을 보장하는 데 기여합니다. 경로가 더 이상 없을 때까지 반복하여 최대 유량을 찾습니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())

board = [[0] * 52 for i in range(52)]
line = [[0] * 52 for i in range(52)]

def mapping(c):
    if 'A' <= c <= 'Z':
        return ord(c) - ord('A')
    return ord(c) - ord('a') + 26

def BFS(start, end, parent):
    visited = [False] * 52
    q = deque([start])
    visited[start] = True

    while q:
        x = q.popleft()
        for i in range(52):
            if not visited[i] and board[x][i] - line[x][i] > 0:
                parent[i] = x
                visited[i] = True
                if i == end:
                    return True
                q.append(i)
    return False

for i in range(n):
    x, y, w = input().split()
    u = mapping(x)
    v = mapping(y) 
    w = int(w)

    board[u][v] += w
    board[v][u] += w

answer = 0
parent = [-1]*52

start = mapping("A")
end = mapping("Z")

while BFS(start, end, parent):
    a = float('inf')
    v = end
    while v != start:
        u = parent[v]
        a = min(a, board[u][v] - line[u][v])
        v = u

    v = end
    while v != start:
        u = parent[v]
        line[u][v] += a
        line[v][u] -= a
        v = u

    answer += a

print(answer)