티스토리 뷰

반응형


#. 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 == -1return 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




반응형
댓글
최근에 올라온 글
최근에 달린 댓글
링크
Total
Today
Yesterday