17471
-
백준 17471번 게리맨더링PS 2020. 3. 5. 19:01
https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 완전탐색 문제입니다. 정점을 선택한 후에 연결여부를 확인해야합니다. 선택은 백트래킹으로 하면 됩니다. 정점 선택은 조합으로 해야겠죠. 그럼 자연스레 2개의 그룹으로 나뉩니다. 확인은 bfs로 하면 됩니다. 2개의 그룹 모두 확인 해야합니다. 하나의 그룹이 모두 연결되어 있다고해도 다른 그룹은 아닐 수 있으니까요. #include #include #include using namespace std; const int I..