축제 게이트가 흘려보낼 수 있는 최대 인원
자바스크립트 코딩테스트 문제로 max-flow 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
축제장 안의 게이트와 통로가 주어질 때, 한 번에 흘려보낼 수 있는 최대 인원을 구하세요.
문제 설명
게이트 0번부터 n - 1번까지 있고, 각 통로는 [from, to, capacity] 형태로 주어집니다.
from게이트에서to게이트로만 이동할 수 있습니다.capacity는 그 통로가 동시에 감당할 수 있는 최대 인원입니다.- 같은 두 게이트 사이에 통로가 여러 개 있을 수 있으며, 이 경우 각각 별도의 통로로 봅니다.
source 게이트에서 sink 게이트까지 보낼 수 있는 인원의 최댓값을 반환하는 maximumFestivalGateFlow 함수를 작성하세요.
제한사항
2 <= n <= 2000 <= passages.length <= 5,000passages[i] = [from, to, capacity]0 <= from, to < nfrom !== to1 <= capacity <= 1,000,0000 <= source, sink < nsource !== sink- 반환값은
source에서sink까지 보낼 수 있는 최대 유량입니다.
예시
- 입력:
n = 4,passages = [[0,1,3],[0,2,2],[1,2,1],[1,3,2],[2,3,4]],source = 0,sink = 3→ 출력:5 - 입력:
n = 3,passages = [[0,1,5],[0,1,2],[1,2,4],[0,2,1]],source = 0,sink = 2→ 출력:5 - 입력:
n = 5,passages = [[0,1,10],[1,2,1],[2,4,10],[0,3,5]],source = 0,sink = 4→ 출력:1 - 입력:
n = 3,passages = [[0,1,7]],source = 0,sink = 2→ 출력:0
힌트
- 단순히 한 경로의 최소 용량만 보면 안 됩니다. 여러 경로로 나누어 흘릴 수 있습니다.
- 이미 사용한 통로를 일부 되돌리는 선택이 필요할 수 있으므로, 잔여 그래프를 함께 관리해야 합니다.
- BFS로
source에서 도달 가능한 레벨을 만들고, DFS로 그 레벨 그래프 안에서 더 보낼 수 있는 유량을 밀어 보세요.
해설
이 문제는 전형적인 최대 유량(max flow) 문제입니다.
각 통로의 수용 인원을 간선 용량으로 보고, source에서 sink로 보낼 수 있는 총 유량의 최댓값을 계산합니다.
단순히 가능한 경로를 하나씩 찾는 방식도 생각할 수 있지만, 경로 선택을 잘못하면 나중에 더 좋은 배치를 막을 수 있습니다. 그래서 유량 알고리즘에서는 항상 잔여 그래프를 둡니다.
1. 잔여 간선 만들기
통로 u -> v에 용량 c가 있다면 그래프에는 다음 두 간선을 넣습니다.
- 정방향 간선:
u -> v, 남은 용량c - 역방향 간선:
v -> u, 남은 용량0
정방향으로 유량 x를 흘리면 정방향의 남은 용량은 x만큼 줄고, 역방향의 남은 용량은 x만큼 늘어납니다.
이 역방향 간선 덕분에 이전에 보낸 유량 일부를 되돌리며 더 좋은 전체 배치로 바꿀 수 있습니다.
2. Dinic 알고리즘 흐름
Dinic 알고리즘은 다음 과정을 반복합니다.
- BFS로
source에서 각 정점까지의 레벨을 계산합니다. sink에 도달할 수 없다면 더 이상 보낼 유량이 없으므로 종료합니다.- 레벨이 정확히 1 증가하는 간선만 따라 DFS를 수행합니다.
- DFS로 가능한 만큼의 blocking flow를 흘립니다.
- 흘린 양을 정답에 누적하고, 잔여 용량을 갱신합니다.
BFS로 만든 레벨 그래프를 쓰면 의미 없는 역방향 탐색을 줄일 수 있고, 같은 레벨 그래프 안에서 더 이상 보낼 수 없을 때까지 유량을 밀어 넣을 수 있습니다.
3. 같은 게이트 사이의 여러 통로
0 -> 1 통로가 용량 5와 2로 두 개 있다면 총 7처럼 볼 수도 있지만, 구현에서는 두 간선을 그대로 추가해도 됩니다.
Dinic의 잔여 그래프는 각 간선을 독립적으로 처리하므로 병렬 통로도 자연스럽게 합산됩니다.
4. 예시 풀이 감각
첫 번째 예시에서는 0번 게이트에서 나가는 총 용량이 3 + 2 = 5입니다.
실제로 다음처럼 총 5명을 보낼 수 있습니다.
0 -> 1 -> 3으로 2명0 -> 2 -> 3으로 2명0 -> 1 -> 2 -> 3으로 1명
따라서 최댓값은 5입니다.
세 번째 예시에서는 source에서 많은 인원이 나갈 수 있어도 1 -> 2 통로의 용량이 1이라 sink까지 이어지는 전체 흐름은 1명으로 막힙니다.
5. 복잡도
Dinic 알고리즘은 일반적인 그래프에서 충분히 빠르게 동작합니다.
이 문제의 제한에서는 인접 리스트와 현재 간선 포인터를 함께 사용하면 브라우저에서도 처리 가능한 수준입니다.
- 정점 수:
V = n - 간선 수:
E = passages.length - 구현 기준 시간 복잡도: 보통
O(V^2 E)상한 안에서 동작 - 공간 복잡도: 잔여 간선을 포함해
O(V + E)
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.