https://www.acmicpc.net/problem/23569
문제요약
- 그래프가 주어짐(n=1000)
- 두 개의 그룹으로 나눌 수 있는가? 그룹내의 노드는 모두 "직접" 연결되어 있어야함
- 크기의 차이를 최소로 나누기
접근법
- 직접 연결된 노드들끼리 묶어서 구성을 해보려고 했는데 쉽지 않음
- 만약에 모든 노드들이 직접 연결되어있다면?
- 어떻게 나누어도 그룹내 노드들은 모두 직접 연결되어 있을 것임
- 차이를 최소로 나누는 방법은 0 또는 1이 될 것임
- 직접 연결이 안된 노드가 있다면? -> 따로 빼서 생각해야함 -> 발상의 시작
- 직접 연결이 안된 노드는? -> 같은 그룹이 될 수 없음 -> 같은 그룹이 될 수 없는 것들은 분리한다 -> 모여 있는 것들은 같은 그룹이 될 수 있는 것들
- 서로 연결이 안되는 경우에 간선을 구성해서 새로운 그래프를 만듬
- 이웃한 노드끼리는 같은 그룹이면 안됨
- 새로 구성한 그래프에서 두 개의 그룹으로 나눌 수 있는지 판단(이분 그래프)
- 두 그룹의 크기를 판단
- 이러한 그래프들이 여러개 있을 것이므로 각각에 대해서 모두 계산
- 그룹의 차이를 이용해서 최소가 되는 경우 계산
- 예를 들어 새로 그래프를 구성해서 두 그룹의 크기를 계산한 결과 다음과 같다고 치면
- (10, 5) : 차이 5
- (1, 2) : 차이 1
- (3, 11) : 차이 8
- A 그룹에 할당되는 값, B 그룹에 할당되는 값으로 경우의 수를 구할 수 있는데, 결국 생각해보면 "차이"만 가지고 계산이 가능함
- 차이 5
- 차이 (5+1) 또는 (5-1)
- 차이 (6+8), (6-8), (5+8), (5-8)
newbieski