Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/2188
2188번: 축사 배정
농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해
www.acmicpc.net
풀이
solved.ac 난이도: Platium 4
이분 매칭 문제들은 최대 유량을 이용하면 간단히 해결할 수 있다.
[네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘
이분 매칭 문제는 두 집합에서의 대응 관계를 해결할 수 있다.
대표적으로 작업 배분을 한다고 생각해보자.
A집합(인원)이 할 수 있는 B집합(작업)들 중 하나 선택하여 배정받는다.
이때 최대한의 작업을 할 수 있도록 A와 B 집합 간의 연결관계(연결된 쌍)를 최대한으로 만드는 것이 이분 매칭 문제이다.
이를 구현할 때 최대 유량을 적용해보면
source에서 A집합의 정점들과 간선을
A집합에서 B집합으로의 간선을
B집합에서 sink로의 간선을 연결하면 된다.
이때 모든 간선의 용량을 1로 설정하면 모든 경로는 유일하게 선택되므로 A와 B의 두 정점 간의 연결 관계를 만들 수 있다.
이를 이번 문제에 그대로 적용하면 소(A집합)가 원하는 축사(B집합)들 중 하나를 선택하여 들어간다.
예제의 입력을 이분 그래프로 표현해보면 다음과 같다.
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

단, 문제 해결을 위해 완전한 최대 유량 알고리즘을 구현하기보다는 이분 매칭에 특화된 DFS 알고리즘을 사용하자.
a_match와 b_match 배열로 매칭 되는 쌍을 서로 저장하여 구현하자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int cow_num, house_num;
vector<vector<int>> adj;
vector<int> a_match, b_match, visited;
bool DFS(int a){
if(visited[a])
return false;
visited[a] = true;
for(int i=0; i<adj[a].size() ; ++i){
int b = adj[a][i];
if(b_match[b] == -1 || DFS(b_match[b])){
a_match[a] = b;
b_match[b] = a;
return true;
}
}
return false;
}
int main(){
ios_base::sync_with_stdio(0);
cin>>cow_num>>house_num;
adj = vector<vector<int>>(cow_num);
int hope_num, house_idx;
for(int i=0; i< cow_num ; ++i){
cin>>hope_num;
for(int j=0;j<hope_num; ++j){
cin>>house_idx;
adj[i].push_back(house_idx);
}
}
a_match = vector<int>(cow_num, -1);
b_match = vector<int>(house_num+1, -1);
int max_matching =0;
for(int start = 0; start<cow_num ; ++start){
visited = vector<int>(cow_num, false);
if(DFS(start))
++max_matching;
}
cout<<max_matching<<'\n';
return 0;
}
|
cs |
이때 17번째 줄의 if문의 조건을 잘 살펴보자.
if(b_match[b] == -1 || DFS(b_match[b]))
OR연산은 앞의 조건이 맞다면 뒤의 조건의 사실 여부에 상관없이 true가 된다.
즉, 뒤의 조건인 DFS(b_match[b])을 실행하기 위해서는 b_match[b] == -1 가 먼저 거짓으로 판정되어야 한다.
b_match[b] == -1가 아닌 경우는 이미 b가 다른 a 집합의 정점과 매칭이 되었다는 것이다.
따라서 DFS(b_match[b])를 호출하여 b와 연결된 a가 다른 b를 선택할 수 있도록 변경해주자.
a정점들의 방문 여부를 저장하는 visited는 무한 루프를 막기 위해서 사용한다.
다음과 같은 이분 그래프에서 이미 a는 1과 b는 2와 연결된 상태를 생각해보자.

이 상태에서 c가 2와 연결 가능한지의 여부를 확인할 때 만약 방문 여부를 저장하지 않는다면
2와 연결된 DSF(b)를 호출하고 b는 1과 연결된 DFS(a)를 호출한다.
이때 a를 다른 정점과 연결 가능하지 여부를 확인하기 위해 다시 2와 연결된 DFS(b)를 호출하여 무한 루프를 돌게 된다.
따라서 방문 여부를 저장해 주자.
참고 서적: 알고리즘 문제 해결 전략(구종만 저)
코드
#include<iostream> | |
#include<queue> | |
#include<string.h> | |
using namespace std; | |
int cow_num, house_num; | |
vector<vector<int>> adj; | |
vector<int> a_match, b_match, visited; | |
bool DFS(int a){ | |
if(visited[a]) | |
return false; | |
visited[a] = true; | |
for(int i=0; i<adj[a].size() ; ++i){ | |
int b = adj[a][i]; | |
if(b_match[b] == -1 || DFS(b_match[b])){ | |
a_match[a] = b; | |
b_match[b] = a; | |
return true; | |
} | |
} | |
return false; | |
} | |
int main(){ | |
ios_base::sync_with_stdio(0); | |
cin>>cow_num>>house_num; | |
adj = vector<vector<int>>(cow_num); | |
int hope_num, house_idx; | |
for(int i=0; i< cow_num ; ++i){ | |
cin>>hope_num; | |
for(int j=0;j<hope_num; ++j){ | |
cin>>house_idx; | |
adj[i].push_back(house_idx); | |
} | |
} | |
a_match = vector<int>(cow_num, -1); | |
b_match = vector<int>(house_num+1, -1); | |
int max_matching =0; | |
for(int start = 0; start<cow_num ; ++start){ | |
visited = vector<int>(cow_num, false); | |
if(DFS(start)) | |
++max_matching; | |
} | |
cout<<max_matching<<'\n'; | |
return 0; | |
} |
'알고리즘 공부 > 백준' 카테고리의 다른 글
[백준] No.1017 - 소수 쌍 (C++, 이분 매칭) (0) | 2021.06.12 |
---|---|
[백준] No.9577 - 토렌트 (C++, 이분 매칭) (0) | 2021.06.11 |
[백준] No.11495 - 격자 0 만들기 (C++, 최대 유량) (0) | 2021.06.09 |
[백준] No.2316 - 도시 왕복하기 2 (C++, 최대 유량, 정점 분할) (0) | 2021.06.02 |
[백준] No.1420 - 학교 가지마! (C++, 최소 컷, 최대 유량, 정점 분할) (0) | 2021.06.02 |