[백준] 17471 게리 맨더링 - JAVA

백준 17471 게리 맨더링 GoldIII - JAVA 📌

https://www.acmicpc.net/problem/17471

문제 설명

문제 풀이

---

접근 💡

- 1 부터 N 까지 숫자를 두 구역으로 나눌 수 있는 모든 경우의 수를 찾는다! < 백트래킹
- 구역을 나누고 한 구역 마다 인접해 있는지 확인한다! < BFS
- 인접해 있다면 두 구역의 인구수 차를 구해 최솟값으로 갱신해준다!

 

첫 번째, 숫자(지역)를 두 구역으로 나눠보자.

for (int i = 1; i <= N / 2; i++) {
	boolean[] visited = new boolean[N + 1];
    combine(1, i, new ArrayList<>(), visited);
}

//두 구역으로 나누는 메서드
public static void combine(int start, int end, ArrayList<Integer> groupA, boolean[] visited) {
	if (groupA.size() == end) {
    	ArrayList<Integer> groupB = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
        	if (!visited[i]) {
            	groupB.add(i);
            }
        }
        return;
    }
    
    for (int i = start; i <= N; i++) {
    	visited[i] = true;
        groupA.add(i);
        combine(i + 1, end, groupA, visited)
        groupB.remove(groupA.size() - 1);
        visited[i] = false;
    }
}

왜 메인 메서드에서 for문의 범위가 N이 아닌 N / 2 일지 생각을 해봐야 한다.

 

N까지 반복을 한다 가정해보자.

- 구역이 나뉠 때 한 구역의 범위가 아래와 같이 될 것이다.

[1], [2,3,4,5,6]

[2], [1,3,4,5,6]

...

[6], [1,2,3,4,5]

...

[1,2,3], [4,5,6]

[1,2,4], [3,5,6]

...

[1,2,3,4,5], [6]

...

바로 위 구역이 나뉘어진 경우를 봐보자. 어랏? 중복이 발생하네!?

이렇게 구역이 나뉜 경우를 이미 탐색을 했을 것이다.

 

따라서.. 메인 메서드에서 for문의 범위를 N까지 해주어야 한다.

그럼 탐색의 마지막은

[4,5,6], [1,2,3] 이 될 것이고 이 경우, 모든 경우를 탐색한 것과 마찬가지가 된다.

 

두 번째, 나뉜 두 구역이 한 구역마다 인접해 있는지 확인 해본다.

public static boolean isLinked(ArrayList<Integer> group) {

    boolean[] visited = new boolean[N];
    Queue<Integer> q = new LinkedList<>();
    q.add(group.get(0));
    visited[group.get(0)];
    int cnt = 1;
    
    while (!q.isEmpty()) {
    	int cur = q.poll();
        for (int link : adjList.get(cur)) {
        	if (group.contains(link) && !visited[cur]) {
            	visited[link] = true;
                q.add(link);
                cnt++;
            }
        }
    }
    
    return group.size() == cnt;
}

인접리스트 adjList 안의 값을 확인하며 group 내 연결요소가 없는지 확인한다. 연결 되어 있다면 cnt를 하나씩 올려주어

모두 연결 되어 있다면 group의 크기와 cnt가 같을 것이고, 이 경우 true를 반환한다.

다르다면 false!

 

세 번째,  인구 수의 차를 구해 최솟값으로 갱신! ... 해 주는 것은 전체 코드에서 확인해보자!

코드 💡

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] people;
    static StringTokenizer st;
    static ArrayList<ArrayList<Integer>> adjList;
    static int ans = Integer.MAX_VALUE;
    static boolean divChk;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());

        people = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            people[i] = Integer.parseInt(st.nextToken());
        }

        adjList = new ArrayList<>();
        adjList.add(new ArrayList<>());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int adjCnt = Integer.parseInt(st.nextToken());
            ArrayList<Integer> adj = new ArrayList<>();
            for (int j = 0; j < adjCnt; j++) {
                adj.add(Integer.parseInt(st.nextToken()));
            }
            adjList.add(adj);
        }

        //구역 나누기
        for (int i = 1; i <= N/2; i++) {
            boolean[] visited = new boolean[N + 1];
            combine(1, i, new ArrayList<>(), visited);
        }

        if (divChk) {
            bw.write(ans + "");
        }
        else {
            bw.write(-1 + "");
        }
        br.close();
        bw.flush();
        bw.close();
    }
    public static void combine(int start, int end, ArrayList<Integer> groupA, boolean[] visited) {

        if (groupA.size() == end) {
            ArrayList<Integer> groupB = new ArrayList<>();
            for (int i = 1; i <= N; i++) {
                if (!visited[i]) {
                    groupB.add(i);
                }
            }
            // 그룹이 나뉘었을 때
            if (isLinked(groupA) && isLinked(groupB)) { //두 그룹 모두 인접인 경우
                int sum_A = 0, sum_B = 0;
                for (int i = 0; i < groupA.size(); i++) {
                    sum_A += people[groupA.get(i)];
                }
                for (int i = 0; i < groupB.size(); i++) {
                    sum_B += people[groupB.get(i)];
                }
                ans = Math.min(ans, Math.abs(sum_A - sum_B));
                divChk = true;
            }
            return;
        }

        for (int i = start; i <= N; i++) {
            visited[i] = true;
            groupA.add(i);
            combine(i + 1, end, groupA, visited);
            groupA.remove(groupA.size() - 1);
            visited[i] = false;
        }
    }
    public static boolean isLinked(ArrayList<Integer> group) {
        boolean[] visited = new boolean[N + 1];
        Queue<Integer> q = new LinkedList<>();
        q.add(group.get(0));
        visited[group.get(0)] = true;
        int cnt = 1;

        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int link : adjList.get(cur)) {
                if (!visited[link] && group.contains(link)) {
                    cnt++;
                    q.add(link);
                    visited[link] = true;
                }
            }
        }
        return cnt == group.size();
    }
}

combine 메서드 안에서 정답을 구하는 과정을 확인 해보자!

 

 

알고리즘 자체는 어렵지 않은데.. 두 구역으로 나누는 방법을 떠올리지 못해 오래 걸렸다..

SW역량테스트 A형 어려워 ㅠㅠ