[BOJ] 백준 17471. 게리맨더링

▶문제설명

[BOJ] 백준 17471. 게리맨더링

https://www.acmicpc.net/problem/17471

▶Hint

---

조합과 DFS를 이용한 부르트포스 문제이다.

문제 해결에 핵심이 되는 두 부분에 대해 설명하고자 한다.

1. 구역 번호 1~N을 두 개의 선거구로 나눈다.

[구역 번호를 두 개의 선거구로 나누는 모든 경우의 수]

구역 번호 1~N에서 1개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-1개를 선거구 B라고 한다. (nC1가지 경우)

구역 번호 1~N에서 2개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-2개를 선거구 B라고 한다. (nC2가지 경우)

구역 번호 1~N에서 3개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-3개를 선거구 B라고 한다. (nC3가지 경우)

...

구역 번호 1~N에서 N-1개를 선택해서 선거구 A라고 하고 나머지 구역 번호 1개를 선거구 B라고 한다.(nCn-1가지 경우)

이 과정에서 next_permutation()을 활용하여 조합을 구현하면 쉽게 해결할 수 있다.

2. 선거구 A와 선거구 B로 나눌 수 있는 모든 경우에 대해, 선거구 A와 B가 모든 구역이 인접한 상태로 구성되어 있는지 확인한다.

선거구 A는 a개의 구역, 선거구 B는 b개의 구역으로 나누어진 상황이라고 했을 때

a개의 구역으로 이루어진 선거구 A의 한 구역에서 DFS를 수행하며 a개의 구역이 인접해있는지 확인하고,

N-b개의 구역으로 이루어진 선거구 b의 한 구역에서 DFS를 수행하며 b개의 구역이 인접해있는지 확인한다.

확인 결과 선거구 A, B 모두 인접한 구역만으로 이루어져있다면 성공적으로 두 선거구로 나눈 것이다.

성공적으로 두 선거구를 나누었을 모든 경우에 대해 두 선거구의 인구 차이를 구하여 정답을 갱신하면 된다.

▶Solution

---

[코드 보기]