[백준] 17779번: 게리맨더링 2 (C++)

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

17779번: 게리맨더링 2

미사여구가 참 많은 문제이다. 심지어 초반에 구역이 어쩌고 저쩌고 나왔던 부분은 문제 푸는 데 아무 필요가 없다.

당시 배가 너무 고파서 제대로 된 사고가 안됐었기 때문에 무지성 brute force로 풀었는데 실제로 무지성으로 푸는 문제가 맞았다.

dfs를 활용할 수도 있지만, 딱히 시간적 이득은 없는 듯 하다.

5번 선거구를 구분하는 것이 포인트였는데, 나의 경우 모든 구역을 순차탐색하면서 한 줄에 경계선을 만난 경우 -> 그 이후를 전부 5선거구로 표시하다가 또 다른 경계선을 만나면 표시를 중단하는 식으로 구현했다. 위 아래 꼭짓점은 패스했다.

근데 생각해 보면 굳이 그렇게 하지 않아도 각 경계선에서 y까지 5선거구로 표시하면 되는 문제였다.

깔끔히 구현하지 못해 아쉬웠다.