[삼성SW기출][백준] 17471. 게리맨더링
2020. 3. 20. 17:33
https://www.acmicpc.net/problem/17471
17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
DFS혹은 BFS를 잘 활용해야하는 문제였습니다.
저는 DFS를 사용해 해결했습니다.
* n이 2일때 예외처리를 해줍니다.
접근방법
- 그룹을 두개로 나누기 위해 1~n/2 개씩 그룹화 해주면, 각 케이스별로 나머지 도시들도 다른 그룹이 됩니다.
- 그룹을 나누는건 백트래킹을 사용해 순열을 조합합니다. (next permutation)
- 그룹이 정해지면 A,B그룹으로 도시들을 리스트에 담고, 각 그룹이 연결되었는지 DFS를 활용해 점검합니다.
- 만약 두 그룹 모두 연결된 상태면 인구수 차이의 최솟값을 업데이트 합니다.
'Algorithm & Data Structure > SWEA' 카테고리의 다른 글
| [백준xSWEA] 13460. 구슬 탈출 2 (review) (0) | 2020.10.09 |
|---|---|
| [삼성SW기출][백준] 17472. 다리만들기 2(Kruskal, unionFind) (0) | 2020.03.24 |
| [삼성SW기출][백준] 17406. 배열 돌리기 4 (0) | 2020.03.19 |
| [SWEA 모의 SW 역량테스트] 5656. 벽돌 깨기 (0) | 2020.03.18 |
| [삼성SW기출] [백준] 3954. Brainf**k 인터프리터 (0) | 2020.03.16 |