BOJ_17471_게리맨더링

1 구분: BFS, DFS, 그래프 이론, 그래프 탐색, 부트포스 알고리즘 언어: Java 전략 1. 지역구 입력 받기 연결 리스트의 형태로 지역구를 받는다. - 노드와 링크를 받을 클래스를 생성하였다. 2. 지역구로 나누기 부분 집합을 구하는 방법으로 지역구 2개로 나눈다 - 부분 집합 하나만 선택하면, 포함되지 않는 것들끼리 또 하나의 부분 집합이 완성 부분 집합의 개수가 0이거나 n개일 경우는 제외한다. 3. 각 부분 집합이 연결되었는지 확인 BFS를 이용하여 각 지역구가 연결 되었는지 확인한다 - 한 점에서 다른 점까지 도달 가능하면 지역구들은 연결되어 있는 것이다. 두 지역구 각각 연결 여부를 확인해야 한다. 4. 차이 구하기 각각의 구역의 인구 수들을 구해서 차이의 최소를 찾는다. 2. 코드 ..

2021.09.24