[백준/JAVA] 17471번: 게리맨더링

📖 문제

17471번: 게리맨더링

 

 

💡  풀이 방식

• 부분 집합 (백트래킹, 재귀) + BFS

필요 자료구조
[전역변수]
- 인구 수 저장용 1차원 int형 배열
- 그래프 정보를 저장하기 위한 그래프 리스트 배열
- 부분 집합용 사용 여부 표시용 1차원 boolean형 배열
- 최솟값

[BFS용]
- 방문할 원소를 저장하는 Integer형 큐
- 방문 표시용 1차원 boolean형 배열 (연결되었는지 확인용)

[두 그룹에 속한 원소들 저장하고, 차이 저장용]
- 구역A 원소들 저장할 Integer형 리스트
- 구역B 원소들 저장할 Integer형 리스트

 

1. 백트래킹을 통해 모든 경우의 부분 집합을 구한다. (재귀)

private static void dfs(int idx) {
    if(idx == N) {
    	// ...
        return;
    }

    // 해당 idx번 사람 선택에 첫 번째 팀에 넣음 (재귀)
    visited[idx] = true;
    dfs(idx + 1);

    // 해당 idx번 사람 비선택에 두 번째 팀에 넣음 (재귀)
    visited[idx] = false;
    dfs(idx + 1);
}

 

 

2. 둘 중 하나라도 공집합인 경우가 없다면, 두 선거구로 나눌 수 있다.

 - 이미 선거구로 뽑혔다면 (visited[i]), 구역 A 리스트에 해당 구역을 추가한다.

 - 선거구로 뽑히지 않았다면 (!visited[i]), 구역 B 리스트에 해당 구역을 추가한다.

 

3. BFS를 통해 나눈 두 그룹 각각 모든 원소들 간 연결이 되어있는지 확인한다.

- 이 때, 방문 가능한 구역은 해당 선거 구에 해당하고, 방문한 적 없는 구역이어야 한다!

if(bfs(group1) &&  bfs(group2))
    getDiff();

 

private static boolean bfs(List<Integer> list) {
    Queue<Integer> q = new ArrayDeque<>();
    q.add(list.get(0));

    boolean[] chk = new boolean[N+1];   // 🔔 방문 배열 따로 생성하기 !!
    chk[list.get(0)] = true;

    while(!q.isEmpty()) {
        int now = q.poll();

        for(int next : A[now]) {
            if(list.contains(next) && !chk[next]) { // ⭐ 선거구에 해당하고,⭐ 방문한 적 없는 경우
                chk[next] = true;
                q.add(next);
            }
        }
    }

    for(int i : list) { // 연결되어있지 않아 방문한 적 없는 원소가 존재한다면 NO
        if(!chk[i]) {
            return false;
        }
    }

    return true;
}

 

 

4. 만약 두 그룹 모두 각 원소들끼리 연결이 되어 있다면, 두 그룹 간 인구 수 차이를 계산하고, 이를 최솟값과 비교해 갱신한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;   // 인구 수 저장 배열
    
    static List<Integer>[] A;
    static boolean[] visited;   // 부분 집합용 배열
    
    static int min = Integer.MAX_VALUE;
   
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        visited = new boolean[N+1]; // 부분 집합용 배열
        
        A = new ArrayList[N+1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        // 각 구역의 인구 수 저장
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 1 ; i <= N ; i++) {
            String[] str = br.readLine().split(" ");
            for(int j = 1 ; j < str.length ; j++) {
                int num = Integer.parseInt(str[j]);
                
                A[i].add(num);
                A[num].add(i);
            }
        }
        
        // 1. 부분 집합 구하기
        dfs(0);
        
        if(min == Integer.MAX_VALUE)
            min = -1;
 
        System.out.println(min);
    }
    
    // 부분집합 만드는 메서드 (재귀)
    private static void dfs(int idx) {
        if(idx == N) {
            List<Integer> group1 = new ArrayList<>();
            List<Integer> group2 = new ArrayList<>();
            
            for(int i = 1 ; i <= N ; i++) {
                if(visited[i])  group1.add(i);
                else            group2.add(i);
            }
            
            if(group1.size() == 0 || group2.size() == 0) // 🔔 공집합 처리 !!
                return;
            
            // 2. 나눈 두 그룹에서 각 그룹의 원소들끼리 연결되어있는지 확인
            if(bfs(group1) &&  bfs(group2))
                getDiff();
            
            return;
        }
        
        // 해당 idx번 사람 선택에 첫 번째 팀에 넣음 (재귀)
        visited[idx] = true;
        dfs(idx + 1);
        
        // 해당 idx번 사람 비선택에 두 번째 팀에 넣음 (재귀)
        visited[idx] = false;
        dfs(idx + 1);
    }
    
    // 해당 그룹의 원소들끼리 연결되어있는지 확인하는 메서드
    private static boolean bfs(List<Integer> list) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(list.get(0));
        
        boolean[] chk = new boolean[N+1];   // 🔔 방문 배열 따로 생성하기 !!
        chk[list.get(0)] = true;
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int next : A[now]) {
                if(list.contains(next) && !chk[next]) { // ⭐ 선거구에 해당하고,⭐ 방문한 적 없는 경우
                    chk[next] = true;
                    q.add(next);
                }
            }
        }
        
        for(int i : list) { // 연결되어있지 않아 방문한 적 없는 원소가 존재한다면 NO
            if(!chk[i]) {
                return false;
            }
        }
        
        return true;
    }
    
    // 두 그룹 간 점수 차 구하고 최솟값 구하는 메서드
    private static void getDiff() {
        int sum1 = 0;
        int sum2 = 0;
        
        for(int i = 1 ; i <= N ; i++) {
            if(visited[i])  sum1 += arr[i];
            else            sum2 += arr[i];
        }
        
        int diff = (int)Math.abs(sum1 - sum2);
        min = Math.min(min, diff);
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

- 지역구 나눌 때 int형 배열에 값을 기록해 활용하셨고,  두 지역으로 나뉘었는지 확인할 때 BFS를 안 쓰고 푸심...>!!!

[BOJ/JAVA] 백준 17417번 : 게리멘더링

 

 

- 이 풀이도 지역 2개로 나눌 때 int형 배열 사용하심

[백준]17417: 게리맨더링 - JAVA

---

💦 어려웠던 점

- 링크와 스타트 문제와 비슷하다 생각했고,, 부분집합 문제인 것과 로직은 맞게 생각했다.

- 그런데 부분 집합을 제대로 구현하지 못 했다.

- 그리고 공집합 처리를 제대로 하지 못 했다!

- BFS 할 때 방문 표시 배열을 따로 작성해 활용하지 않았다,,,

- BFS에서 큐에 다음 값 추가할 때, 선거구 지역에 해당하는지 확인하는 것을 놓쳤다 ! 

이 정도면 다 어려웠다..라고 쓰는 게 빠를 듯

 

 

 

🧐 새로 알게 된 내용

- 부분집합 구하는 방법과 재귀 ver.과 조합 ver.의 차이를 이번에 제대로 깨달았다 (이번 문제는 재귀 ver.)

 

 

1회독	2회독	3회독	4회독	5회독
V	240228

 

 

(+ 2회독 240228)

55분 소요,,

부분집합 (재귀)과 bfs를 함께 써야하는 문제임을 기억하는데 40분 정도 걸린 듯..

 

 

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;
    static List<Integer>[] A;
    static boolean[] selected;
    
    static int diff = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        arr = new int[N + 1];   // 각 구역의 인구
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        A = new ArrayList[N+1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        // 각 구역, 인접 정보
        for(int i = 1 ; i <= N ; i++) {
            String[] str = br.readLine().split(" ");
            
            int cnt = Integer.parseInt(str[0]);
            
            for(int j = 1 ; j < str.length ; j++) {
                int num = Integer.parseInt(str[j]);
                A[i].add(num);
                A[num].add(i);
            }
        }
        
        selected = new boolean[N+1];
        
        // 두 선거구로 나누기 -> 부분 집합
        dfs(1, 0);  // idx , depth
        System.out.println(diff == Integer.MAX_VALUE ? -1 : diff);
    }
    
    private static void dfs(int idx, int depth) {
        // 종료 조건
        if(idx == N) {
            ArrayList<Integer> list1 = new ArrayList<>();
            ArrayList<Integer> list2 = new ArrayList<>();
 
            for(int i = 1 ; i <= N ; i++) {
                if(selected[i])
                    list1.add(i);
                else
                    list2.add(i);
            }
            
            // 둘 중 하나라도 공집합이면 pass
            if(list1.size() == 0 || list2.size() == 0)  return;
            
            // 각 선거구 간 연결되어있는지 확인
            if(!bfs(list1) || !bfs(list2))  return;
            
            int sum1 = 0;
            int sum2 = 0;
            for(int x : list1)  sum1 += arr[x];
            for(int x : list2)  sum2 += arr[x];
            
            diff = Math.min(diff, Math.abs(sum1 - sum2));
            return;
        }
        
        // 비선택한 경우
        dfs(idx + 1, depth);
        
        // 선택한 경우
        selected[idx] = true;
        dfs(idx + 1, depth + 1);
        selected[idx] = false;
    }
    
    private static boolean bfs(List<Integer> list) {
        boolean[] visited = new boolean[N+1];
        visited[list.get(0)] = true;
        
        Queue<Integer> q = new ArrayDeque<>();
        q.add(list.get(0));
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int next : A[now]) {
                if(list.contains(next) && !visited[next]) { // ⭐해당 리스트에 속한 ⭐ 값이고, 방문한 적 없는 경우
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
        
        for(int num : list) {
            if(!visited[num])
                return false;
        }
        
        return true;
    }
}
 

 

 

---

(참고)

✔ 풀이 참고

[백준 17471] 게리맨더링 (JAVA)

 

✔ 부분 집합 vs 멱 집합 개념

[Java]부분 집합(Subset)과 멱집합(Power Set)

부분집합 PowerSet (Java)

https://bono039.tistory.com/1101

 

 

🔗 유사 문제 : 백준 15661 링크와 스타트

[백준/JAVA] 15661번: 링크와 스타트