개요
Network flow, 비선형 그래프
이분 그래프의 최대유량 구하기
접근
이분
이분 이라는 단어를 보고 파블로프의 개마냥 이분탐색을 생각하기 쉽다. 이분과 매칭이라니, 리스트를 절반으로 나누면서 탐색하는 문제인가? 하는 생각을 하기 쉽다. 하지만 이분탐색과는 단 하나도 관련이 없다.
우선 그래프란, 컴퓨터가 데이터를 이해하고 인간이 데이터를 처리하기 쉽도록 만든 데이터의 연결관계이다. 이걸 자료구조라고 하고, 연결 방식에 따라 선형과 비선형으로 나뉘는데 그래프는 이 중 비선형 구조에 해당한다. 선형 구조는 리스트, 스택, 큐처럼 인접한 원소의 인덱싱이 선형적인 관계를 가지는 것들이라 생각하면 쉽다.
연결 구조를 나타낼 수만 있으면 그래프가 되기 때문에 배열, 행렬도 모두 그래프가 된다. 모든 지점을 서로 이동하는 비용이나 경로의 수를 2차원으로 나타내면 인접행렬이 된다. 일반적인 BFS나 DP에서 사용되는 행렬도 사실은 전부 그래프이다. 티어별로 사용하는 그래프 유형이 조금 다른데,
- 일반적인 골드 그래프 문제에서 그래프는 다차원 인접행렬을 사용한다. N이 작기 때문에 적은 메모리로 커버가 된다.
- 조금 특수한 골드 문제나 플래 하위에서는 인접리스트를 사용한다. 대표적으로 1753번이 그렇다. N이 10000을 넘어가면 1e8개 정수를 저장해야 하고 이 공간이 부족하기 때문이다.
C언어를 사용한다면 여기부터 머리가 뜯어진다. 기본적으로 stack을 제공하기 않기 때문에 나는 이쯤부터 C++로 넘어왔다. - 플래부터는 트리와 그래프를 사용한다. 사이클의 유무를 제외하고 둘은 큰 차이가 없고, 구현은 인접리스트나 배열을 이용한다. 이 부분은 나중에 하나씩 다루어보려고 한다.
그래서 이분그래프란 무엇인가? 그래프의 연결구조가 두 덩어리로 나누어지는 것을 말한다. PS를 하다보면 union find에 대해서는 한번쯤 들어볼 것이다. 흔히 disjoint set이라 하는데 이거랑 느낌이 비슷하다.
Union find를 통해 그룹을 만들때는 u에서 v까지 이동할 수 있다면 한 그룹으로 포함한다. 즉 그룹 내의 모든 정점에 대해 연결구조가 있다.
반면 이분그래프는 어떤 정점을 두 그룹 A,B로 나누었을때 A의 경로가 모두 B를 향해 있는 경우이다. 모든 간선이 두 그룹 사이에서만 존재한다는 것이다.
그림으로 나타내자면 이렇다. 결론은 모든 간선이 두 그룹 내의 원소를 연결하는 경우를 이분그래프라고 한다.
매칭
- 매칭이라는 단어는 그래프를 연결한다는 것인데, 사용가능한 간선 중 일부를 선택하는 것이라 생각하면 된다. 실생활에서는 그래프를 최대로 연결하는 것이 이득인 경우가 많다. 어떤 사용자를 서버에 접속시킬 때 최대한 많은 사용자를 접속시키는 게 좋기 때문. 그래서 매칭은 일반적으로 최대매칭을 말한다.
- 그래프의 정점을 연결하는 간선을 하나의 파이프라 생각하고, 파이프에 지나갈 수 있는 유량이 정해져 있다고 하자. 물과 빨대로 생각하면 쉽다
- 만약 비용이 있다면 최소 비용으로 간선을 연결해야 하고 이걸 최소비용 최대 유량 문제라 한다. 빨대의 굵기가 다를 때 서로 다른 음료를 최대한 많이 마셔야 한다. 근데 옆집 음료를 마셔도 된다.
- 비용이 정해져있지 않다면? 그냥 최대유량 문제가 된다. 같은 빨대로 서로 다른 음료를 최대한 많이 마셔야 한다. 마찬가지로 옆집의 음료를 마셔도 된다.
- 만약 그래프가 이분그래프라면? 즉 정점이 두 개의 그룹으로 나뉘면서 모든 간선이 두 그룹을 연결하는 경우는? 최대 유량 중 특수한 경우인 이분매칭 문제가 된다. 같은 빨대로 서로 다른 음료를 마시는데 옆집이 없다.
- 이 중 두 번째 최대 유량 문제를 해결하는 알고리즘이 Edmonds-Karp 알고리즘이다. 이 부분은 더 공부해서 추가로 다룰 예정이다.
- 이 에드몬드-카프를 응용하면 이분그래프에서 쉽게 최대 매칭을 구할 수 있다.
- 일반적으로 재귀를 활용한다. 원리는 백트래킹과 비슷하고, 출력은 연결 가능여부이다.
- 두 그룹 A,B가 있다고 할 때, Ai와 Aj에 대해 Ai,Aj가 모두 원하는 Bk가 있다고 하자. 우선 Ai와 Bk를 연결한다. 이때 Aj의 연결을 Bk로 바꾸었을 때 Ai의 대안이 있다면 Aj-Bk 연결이 유효하다.
- 이때 Ai가 대안을 골랐을때 이미 연결된 B라면? 그것 또한 재귀적으로 판단한다. 따라서 유효함에 대한 판단은 원하는 B가 중복되는 모든 A를 재연결 했을 때 가능여부가 된다.
- 이게 말이 어려운데 백트래킹에서 중심적으로 다루었던 다음단계가 가능한가? 에 대한 생각을 해보면 크게 어렵지 않다. 쉽게 생각해서 방에 들어갈 때 사람이 있으면 내쫓는다. 근데 계속 내쫓다가 남은 방이 없으면? 못들어가고 다 어떻게든 다른 방을 찾으면 순서대로 내쫓고 들어가버린다.
미친 왕게임 알고리즘 - 마지막으로 모든 재연결 과정에서 A에 대해 방문체크를 한다. 재귀적으로 가장 문제가 있는 지점부터 재연결되기 때문인데, 그러면 한 번씩 재연결해주는 것이 최적의 연결이 된다.
결론은 어렵다. 백트래킹과 유사하다는 생각을 잘 해줘야 하는 개념이 되겠다.
Source code
bool can(int a) {
if (vis[a]) return 0;
vis[a]=1;
for (auto b:adj[a])
// B가 비어있으면 당연히 됨
// 아니면 Ai(=B[b]) 에 대한 대안이 있으면 됨
if (!B[b]||can(B[b])) {
A[a]=b,B[b]=a;
return 1;
}
return 0;
}
int match() {
int cnt=0;
for (int i=1;i<=n;i++)
if (!A[i]) {
fill(vis,vis+N,0);
cnt+=can(i);
}
return cnt;
}관련문제
P4 11375 열혈강호 : 풀이
P4 2188 축사 배정 : 풀이
P4 11376 열혈강호 2 : 풀이
P4 1298 노트북의 주인을 찾아서 : 풀이
P4 17481 최애 정하기 : 풀이
P4 2191 들쥐의 탈출 : 풀이
P4 14433 한조 대기 중 : 풀이
P3 1017 소수 쌍 : 풀이
P3 14398 피타고라스 수 : 풀이
P2 1348 주차장 : 풀이
댓글