[BOJ] 삼성 sw 역량 테스트 기출 :: 17779번 게리맨더링 2 (java)

BOJ 17779번 게리맨더링 2 문제 자바(java) 풀이

• 랭크 : 골드4
• 백준 17779번 게리맨더링 2

문제 정리

1. 재현시의 크기 NxN
2. 5개의 선거구로 나누어야 함
3. 각 구역은 5개의 선거구 중 하나에 포함되어야 함
4. 선거구는 적어도 구역 하나를 가져야 함
5. 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 함
6. 인접한 구역을 통해 갈 수 있으면 연결되어 있다고 본다.
7. 선거구에 있는 구역들은 모두 그 내에서 연결되어 있어야 한다.
8. 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자
   
   
   

문제 풀이

문제에서 주어진 대로 선거구를 정확히 나누기만 하면 쉬운 문제이다.
다만 처음에 0번 인덱스부터 했더니 헷갈려서 좀 걸렸다...
헤맸는데도 1시간 정도 걸린것 같다. 삼성 기출 중엔 쉬운 편인듯
디버깅 할때는 위 그림과 같은 상황을 맞추고 제대로 나누어지는지 확인하였다. (i=2, j=4, k=2, q=2)

1칸 더 잡고 1번 인덱스 부터 하니 에러는 없어졌다.
그리고 경계선 안쪽을 5번 선거구로 잘 표시하면 된다.
그리고 선거구 별로 모두 더하여 최대 인구와 최소 인구의 차이를 구하고 min 값을 update한다.
중요 표인트는 모든 경우를 검사하는데 그 때 x,y,d1,d2를 문제에 주어진 조건이 맞는지 먼저 확인하는게 중요한 것 같다.

백준 17779번 게리맨더링 2 java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
class Main {
    static int[][] map;
    static int N;
    static int min;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N+1][N+1];
        
        for(int i=1; i<=N; i++) {
            String[] temp = br.readLine().split(" ");
            for(int j=1; j<=N; j++) {
                map[i][j] = Integer.parseInt(temp[j-1]);
            }
        }
        
        min = Integer.MAX_VALUE;
        // (x,y) 정하기
        // d1, d2 정하기 길이는 1이상
        // x + d1 + d2 <= N check
        // 1 <= y-d1
        // y+d2 <= N
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                for(int k=1; k<=N; k++) {
                    for(int q=1; q<=N; q++) {
                        if(i + k + q > N) continue;
                        if(1 > j - k) continue;
                        if(j + q > N) continue;
                        
                        divide(i, j, k, q);
                    }
                }
            }
        }
        
        System.out.println(min);
    }
    
    public static void divide(int x, int y, int d1, int d2) {
        int[][] check = new int[N+1][N+1];
 
        // 경계선 나누기
        for(int i=0; i<=d1; i++) {
            check[x+i][y-i] = 5; 
        }
        
        for(int i=0; i<=d2; i++) {
            check[x+i][y+i] = 5;
        }
        
        for(int i=0; i<=d2; i++) {
            check[x+d1+i][y-d1+i] = 5;
        }
        
        for(int i=0; i<=d1; i++) {
            check[x+d2+i][y+d2-i] = 5;
        }
        
        // 경계선 안쪽
        boolean start = false;
        for(int i=x+1; i<x+d1+d2; i++) {
            for(int j=1; j<=N; j++) {
                if(start) {
                    // 오른쪽 경계선 도달
                    if(check[i][j] == 5) {
                        start = false;
                        break;
                    }
                    check[i][j] = 5;
                }
                
                // 왼쪽 경계선
                if(check[i][j] == 5) {
                    start = true;
                }
            }
        }
        
        // 1번 선거구
        for(int i=1; i<x+d1; i++) {
            for(int j=1; j<=y; j++) {
                if(check[i][j] == 5) continue;
                check[i][j] = 1;
            }
        }
        
        // 2번 선거구
        for(int i=1; i<=x+d2; i++) {
            for(int j=y+1; j<=N; j++) {
                if(check[i][j] == 5) continue;
                check[i][j] = 2;
            }
        }
        
        // 3번 선거구
        for(int i=x+d1; i<=N; i++) {
            for(int j=1; j<y-d1+d2; j++) {
                if(check[i][j] == 5) continue;
                check[i][j] = 3;
            }
        }
        
        // 4번 선거구
        for(int i=x+d2+1; i<=N; i++) {
            for(int j=y-d1+d2; j<=N; j++) {
                if(check[i][j] == 5) continue;
                check[i][j] = 4;
            }
        }
        
        int diff = getDiffPopulation(check);
        min = min > diff ? diff : min;
    }
    
    public static int getDiffPopulation(int[][] check) {
        int[] sum = new int[5];
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                sum[check[i][j]-1] += map[i][j];
            }
        }
        
        Arrays.sort(sum);
        return sum[4] - sum[0];
    }
}