[BOJ][C++] 17471 게리맨더링
문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 두 팀으로 나누되, 갯수가 정해져있지 않은 조합 문제입니다. 코드가 다소 깔끔하지 못한 점 양해 부탁드립니다. 크게 세 단계로 나누어 풀이했습니다. 1. 두 팀으로 나누기 2. 나눠진 팀의 연결 상태 확인 3. 인구 차이 최소값인지 확인 1. 두 팀으로 나누기 (DFS) DFS로 팀을 나눕니다. team배열에 0과 1로 구분을 해줍니다. 이때, [0,0,0,1,1,1] 과 [1,1,1,0,0,0]은 같은 결..
2020. 4. 16.