백준 6086 - 최대 유량 + 알고리즘 풀이를 위한 개념 정리
3 minute read
문제링크
문제설명
- 자세한 설명은 링크를 참고한다.
- 양방향 그래프의 최대 유량 문제
- 배수관이 병렬, 직렬로 연결되며 문제 설명이 다소 복잡하지만, 결론적으로 각 노드 간의 연결 관계를 고려하여 목적지까지 흘려보낼 수 있는 최대 유량을 계산하는 문제이다.
최대 유량 문제 개념 정리
참고 블로그
- 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이라고 한다.
- 용량(Capacity)
- c(u,v) 는 정점 u에서 v로 가는 간선의 용량(가중치)라고 한다.
- 유량(Flow)
- f(u,v)는 정점 u에서 v로의 간선에 실제로 흐르는 유량을 의미한다.
- 잔여 용량(Residual Capacity)
- 간선의 용량과 유량의 차이를 의미한다.
- r(u,v) = c(u,v) - f(u,v)
- 소스(source)
- 유량이 시작되는 정점으로 모든 유량은 소스에서부터 싱크로 흐르게 된다.
- 싱크(sink)
- 모든 유량이 도착하는 정점이 싱크이다.
- 네트워크 유량 알고리즘은 소스에서 싱크로 흐를 수 있는 최대 유량을 계산한다.
- 증가경로(Aumented Path)
- 최소 1의 유량이 흐를 수 있는 출발점에서 도착점까지 가는 경
- 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)
- 증가경로가 나오지 않을 때까지 유량을 그리디하게(최대 잔여 용량에 맞게) 흘려주는 방식
- 1-2-4-7 경로를 찾은 경우 위와 같은 그래프가 만들어지고, 간선 1-2의 유량이 용량에 도달했으므로 증가 경로는 더 이상 간선 1-2를 포함할 수 없다.
- 간선 1-3을 포함하는 증가 경로인 1-3-6-7을 찾고, 흐를 수 있는 최대 유량인 4를 흘려준 그림은 다음과 같다.
- 마찬가지로 간선 1-4를 포함하는 증가 경로인 1-4-7을 찾는 경우 4-7 에 유량 3이 흐르고 있으므로 최대 1까지만 더 흘려줄 수 있다.
- 이런 상태에서 최대 유량은 8이 된다.
- 중요한 점은 찾게 되는 증가경로의 순서에 따라 미처 발견하지 못하는 증가경로가 존재할 수 있다는 점이다.
- 1-2-4-7 에 흐르는 유량을 우회할 수 있다면 (1-2-5-7) 1-4-7 의 유량을 늘릴 수 있었을 것이다.
- 아래는 실제 가능한 최대 유량인 11을 구하는 방법이다.
- 에드몬드-카프 알고리즘
- 위와 같은 개념은 유량 상쇄 를 적용하여 기존의 간선과 반대 방향인 용량이 0인 간선을 추가하여 해결할 수 있다.
- 양방향 그래프의 경우 용량을 똑같이 설정한다.
- 만약 기존의 간선에 유량 n이 흐르고 있다면 반대 방향의 간선에는 유량 -n이 흐른다고 판단한다.
- 이렇게 되면 반대 방향의 간선에 n만큼의 여유 용량이 생기므로, 해당 간선에 유량을 흘려줄 수 있다.
- 반대 방향의 간선에 유량이 흐른다 == 기존 간선에 있던 유량을 취소하고 우회한다.
- 💡 DFS vs BFS
- 특정 조건에 의해 발생하는 최적화 문제에 있어서 BFS 가 유리하다.
- 만약 다음과 같은 그래프에서 DFS로 증가 경로를 찾아간다고 생각해보자.
- s->a->b->t로의 경로를 증가 경로로 찾았다면 경로 중 최솟값인 1만이 새로운 유량으로 흐를 것이다.
- 이제 DFS로 s->b->a->t의 경로를 찾았다면 이번에도 추가되는 유량은 1일 것이다.
- 증가 경로를 찾는 과정은 source에서 sink로의 경로 중 더 이상 유량을 흘려보낼 수 없을 때까지이므로 s->a->b->t와 s->b->a->t의 경로가 번갈아 찾아지면서 최대 유량인 1000회 동안 반복한다.
- 하지만 BFS를 사용하면 source에서 sink로의 최단 경로만 찾으므로 이러한 예외가 발생하지 않는다.
구현
#include <iostream>
#include <vector>
#include <memory.h>
#include <cctype>
#include <queue>
#include <climits>
#include <algorithm>
#define MAX_ARR 52 // 알파벳 대문자(0~25) + 소문자(26~51)
using namespace std;
int N;
int capacity[MAX_ARR][MAX_ARR];
int flow[MAX_ARR][MAX_ARR];
vector<int> graph[MAX_ARR];
void Init()
{
memset(capacity, 0, sizeof(capacity));
memset(flow, 0, sizeof(flow));
}
int GetMaxFlowAmount(int source, int sink)
{
int retTotalAmount = 0;
while (true)
{
vector<int> parent(MAX_ARR, -1); // 어떤 정점에서 온건지 히스토리를 저장
queue<int> q;
q.push(source);
parent[source] = source;
while (!q.empty())
{
int curNode = q.front();
q.pop();
for (int i = 0; i < graph[curNode].size(); i++)
{
int nextNode = graph[curNode][i];
if (capacity[curNode][nextNode] - flow[curNode][nextNode] > 0 && parent[nextNode] == -1)
{
parent[nextNode] = curNode;
q.push(nextNode);
}
}
}
if (parent[sink] == -1) break; // 증가 경로가 없는 경우
int amount = INT_MAX;
for (int p = sink; p != source; p = parent[p])
{
amount = 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;
}
retTotalAmount += amount;
}
return retTotalAmount;
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
Init();
cin >> N;
for (int i = 0; i < N; i++)
{
char node1, node2;
int weight;
cin >> node1 >> node2 >> weight;
int idx1, idx2;
if (isupper(node1))
{
idx1 = node1 - 'A';
}
else
{
idx1 = node1 - 'a' + 26;
}
if (isupper(node2))
{
idx2 = node2 - 'A';
}
else
{
idx2 = node2 - 'a' + 26;
}
graph[idx1].push_back(idx2);
graph[idx2].push_back(idx1);
capacity[idx1][idx2] += weight;
capacity[idx2][idx1] += weight; // 역방향 간선 (for 유량 상쇄)
}
int ans = GetMaxFlowAmount(0, 25);
cout << ans << endl;
}
Leave a comment