풀이
두 그룹이 있을 때, 모든 간선이 가중치가 1이고 다른 그룹으로만 향하는 그래프를 Bipartite Graph 라고 한다.
이 때, 간선을 통해 다른 정점을 점유한 상태를 matching한다고 하며 Bipartite Graph에 대한 matching을 Bipartite Matching이라고 한다.
즉, 간선의 가중치가 전부 1인 Bipartitle Graph에서 maximun flow을 구해주는 문제는 maximun matching을 구해주는 문제와 동일하다.
때문에 간단하게 DFS를 이용해 O(VE), O((N+M)E) 안에 구현하는 방법을 사용할 수 있다.
최종적으로 연결된 정점을 기록할 match 배열과, 바로 매칭이 되지 않은 경우(다른 정점과 이미 매칭된 경우) 현재 정점을 최종적으로 매칭하기 위해 다른 정점이 이미 방문(매칭)했는지 기록하기 위한 visited 배열을 사용했다.
또한, 최대 매칭이 매칭할 그룹의 개수와 일치한다면, 더 이상의 탐색은 불필요하다.
dfs를 살펴보자.
그룹 N의 정점에서 이어진 그룹 M의 정점들에 대해 탐색을 진행하면서 방문을 처음한 경우(해당 정점에 대해)에 이전 정점에 대해 매칭이 되지 않았거나( not match[v2] ), 이미 다른 정점에 의해 매칭되어 이전 정점이 다른 정점을 선택할 수 있는 경우( dfs(match[v2]) ) 이면 현재 정점이 매칭하고자 하는 정점과 무사히 매칭이 된다.
만약 반복문을 통해 그룹 모든 정점이 매칭이 되지 않았다면 False을 반환한다.
생각보다 오래걸린다.
좀 더 빠르게 매칭을 해보자.
이전 정점에 대해 매칭이 되지 않은 경우( not match[v2] ) 우선적으로 현재 정점과 연결을 하고,
만약 매칭이 되지 않았다면, 다른 정점의 매칭상태를 변경해야 한다.
기존에는 dfs(match[v2])를 통해 다른 정점에 대한 탐색을 무조건 시도했다면 이번에는 dfs를 호출하기 전에 미리 확인하는 방법이다.
visited[match[v2]]를 통해 dfs를 수행하는 것이 적절한지 판단해주고 진행해주자.
문제에서 N, M에 대해 N <= M이라는 조건이 없으니 배열의 크기를 N, M의 최댓값으로 설정해주자.
빨라졌다.
소스코드
출처
11375번: 열혈강호
강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 28224] Final Price [Python] (0) | 2023.06.15 |
|---|---|
| [백준 1298] 노트북의 주인을 찾아서 [Python] (0) | 2023.06.14 |
| [백준 9576] 책 나눠주기 [Python] (0) | 2023.06.14 |
| [백준 21335] Another Eruption [Python] (0) | 2023.06.12 |
| [백준 21736] 헌내기는 친구가 필요해 [Python] (0) | 2023.06.10 |