티스토리 뷰
반응형
#. Problem
* The copyright in this matter is in BOJ
#. Resolution Process
1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it
#. Solve
중요한 포인트는
구역을 두 개의 선거구로 나눠야 한다는 것이다.
단, 조건을 잘 봐줘야 한다.
1. 각 구역은 두 선거구 중 하나에 포함
2. 한 선거구에 포함되어있는 구역은 모두 연결
단계별로 생각해보면
1. 부분집합으로 두 개의 선거구로 나눈다.
2. 나뉘어진 선거구에 포함된 구역이 모두 연결되어있는지 확인
3. 다 연결되어있다면 인구 차이를 구하고, 최소 결과를 갱신
#. Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class BOJ17471 { static int N, res = 987654321, population[]; static ArrayList<Integer>[] adj; static boolean isAreaA[]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); population = new int[N + 1]; adj = new ArrayList[N + 1]; // 인구 정보 입력 st = new StringTokenizer(br.readLine()); for (int i = 1; i <= N; i++) { population[i] = Integer.parseInt(st.nextToken()); adj[i] = new ArrayList<>(); } // 인접한 구역 정보 입력 for (int i = 1; i <= N; i++) { st = new StringTokenizer(br.readLine()); int size = Integer.parseInt(st.nextToken()); for (int j = 0; j < size; j++) { adj[i].add(Integer.parseInt(st.nextToken())); } } isAreaA = new boolean[N + 1]; selectA(1); System.out.println(res == 987654321 ? -1 : res); } /** * 부분집합으로 두 개의 선거구 나누기 * @param idx 구역 index */ private static void selectA(int idx) { // A선거구에 해당하는 구역을 모두 선택했다면 if (idx == N + 1) { // 각 선거구에 포함된 구역이 모두 연결되었는지 확인 if (check()) { // 연결되었다면 int sumA = 0, sumB = 0; for (int i = 1; i <= N; i++) { if (isAreaA[i]) sumA += population[i]; else sumB += population[i]; } res = Math.min(res, Math.abs(sumA - sumB)); } return; } // 이 구역을 A선거구로 선택 isAreaA[idx] = true; selectA(idx + 1); // 이 구역을 A선거구로 미선택 isAreaA[idx] = false; selectA(idx + 1); } /* * 각 선거구에 포함된 구역이 모두 연결되었는지 확인 */ private static boolean check() { boolean[] visited = new boolean[N + 1]; int areaA = -1; // A선거구 구역에 포함된 한 구역을 찾기 for (int i = 1; i <= N; i++) { if (isAreaA[i]) { areaA = i; break; } } int areaB = -1; // B선거구 구역에 포함된 한 구역을 찾기 for (int i = 1; i <= N; i++) { if (!isAreaA[i]) { areaB = i; break; } } // 선거구에 포함된 구역이 없다면 false // 각 구역은 두 선거구 중 하나에 포함 if (areaA == -1 || areaB == -1) return false; Queue<Integer> q = new LinkedList<>(); // 먼저 A 선거구에 포함된 구역들이 모두 연결되었는지 확인 q.add(areaA); visited[areaA] = true; while (!q.isEmpty()) { int now = q.poll(); // 현재 구역과 연결된 구역들을 확인 for (int i = 0; i < adj[now].size(); i++) { // 이미 확인한 곳이면 pass if (visited[adj[now].get(i)]) continue; // A 구역이 아니면 pass if (!isAreaA[adj[now].get(i)]) continue; visited[adj[now].get(i)] = true; q.add(adj[now].get(i)); } } // B 선거구에 포함된 구역들이 모두 연결되었는지 확인 q.add(areaB); visited[areaB] = true; while (!q.isEmpty()) { int now = q.poll(); // 현재 구역과 연결된 구역들을 확인 for (int i = 0; i < adj[now].size(); i++) { // 이미 확인한 곳이면 pass if (visited[adj[now].get(i)]) continue; // B 구역이 아니면 pass if (isAreaA[adj[now].get(i)]) continue; visited[adj[now].get(i)] = true; q.add(adj[now].get(i)); } } // 한 곳이라도 연결되지 않았다면 for (int i = 1; i <= N; i++) { if (!visited[i]) return false; } return true; } } | cs |
반응형
'PS > Problem_Solving' 카테고리의 다른 글
[BOJ] 17472.다리 만들기 2(백트래킹, BFS).java (0) | 2020.09.07 |
---|---|
[BOJ] 17136.색종이 붙이기(백트래킹, 시뮬레이션).java (0) | 2020.09.07 |
[BOJ] 17779.게리맨더링2(시뮬레이션).java (0) | 2020.09.03 |
[BOJ] 3184.양(DFS,BFS).java (0) | 2020.09.02 |
[BOJ] 19535.ㄷㄷㄷㅈ(그래프).java (0) | 2020.09.02 |
댓글