ps:problems:boj:16544
목차
Colorgraph
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 16544 |
| 문제명 | Colorgraph |
| 레벨 | 다이아몬드 2 |
| 분류 |
글로벌 민컷 |
| 시간복잡도 | O(V^3) |
| 인풋사이즈 | V<=250 |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 31912KB / 244ms |
| 최고기록 | 244ms |
| 해결날짜 | 2023/11/28 |
풀이
- Global Minimum Cut를 이용해서 계산하는 문제이긴 한데, 케이스워크가 상당히 복잡한 편이다. 하나씩 따져보자.
- 먼저 N이 3인 경우와 N이 4이상인 경우로 구분하자.
- N=3 일때에는, 블루/레드가 모두 끊겨있거나, 블루/레드가 모두 연결되어있는 경우는 불가능하다. 만들수 있는 상태는 (1,0)이나 (0,1) 뿐이다. N이 작으므로, 만드는 방법은 간단히 찾을수 있다.
- N>=4 일때에는, 우선 블루/레드가 모두 끊겨있는 것은 불가능하다. 한쪽이 끊기면 다른쪽은 연결되게 되어있다. 따라서 만들어야 하는 상태가 (0,1)이나 (1,0)이어서 한 색깔이 끊어져야 하는데 현재 그 색깔이 연결되어있는 경우에는, 그 색깔을 끊는데만 주력하면 된다. 그 색깔을 끊으면 다른 색깔은 자연적으로 연결된다.
- 연결되어있는 색깔을 최소 비용으로 끊는 것은, 그 색깔의 엣지들로만 이루어진 그래프에서 Global mincut를 구하면 된다. 시간복잡도는 O(V^3).
- 만들어야 하는 상태가 (1,1)인 경우일때는 또 복잡하다. 현재 상태가 레드가 끊어져있는 상태라고 가정하자. 생각할수 있는 방법은 레드 그래프에서 연결된 컴포넌트들을 찾은다음, 컴포넌트들을 연결하는 레드 엣지를 추가하는 것이다. 컴포넌트가 n개라면 n-1의 엣지만을 추가해서 레드 그래프를 모두 연결시켜줄수 있다.
- 그런데.. 이 과정에서 블루 그래프가 끊기는 경우가 없는지를 생각해봐야 한다. 여기에 해당되는 유일한 경우는, 레드 그래프에서 어떤 1개의 노드 u만 따로 떨어져 있고 나머지 V-1개의 노드들은 연결되어 있을때, u를 다른 노드 v와 연결시켰더니, v와 다른 노드들 사이에 블루 엣지가 없어지는 경우이다. 즉, v가 처음에 블루엣지 1개와 레드엣지 V-2 개를 갖고 있는 상황이다. u를 연결시켜줄 노드 v를 찾을때, 아무 노드나 찾지 말고 레드 엣지의 갯수가 V-2 보다 작은 노드 v를 찾아서 연결해주면 블루 그래프가 끊기는 일 없이 1개의 엣지만 추가해서 레드 그래프를 연결해줄수 있다.
- 하지만 이게 끝이 아니다. V-1개의 노드들이 완전그래프를 이루어서, 모든 노드들이 레드엣지를 V-2개씩 들고 있는 경우가 있을수도 있다. 이때는 누구와 연결시켜도 그 노드는 블루 연결이 끊어지게 된다. 그래서 추가적으로 레드엣지를 블루엣지로 한번 더 바꿔줘야한다. 이 경우에는 (u,v)를 레드로 바꿔주고 (v,w) 를 블루로 바꿔주면 원하는 상태로 만들어줄 수 있다.
- 케이스웍이 복잡하긴 하지만, 시간복잡도가 많이 큰 작업은 아니다. 총 시간복잡도는 global mincut를 구하는 O(V^3)에 바운드된다.
코드
- 다이아몬드 이상은 코드 생략
- Dependency: teflib.graph.GlobalMincut
ps/problems/boj/16544.txt · 마지막으로 수정됨: 2023/12/10 14:18 저자 teferi
토론