[java]게리맨더링 2 - 백준17779

문제

• 게리맨더링 2(백준17779)

풀이

문제 해석을 하자면,

• 문제만 잘 이해하면 간단한 구현 문제
• 주어진 조건을 그대로 적용해서 구현하면 된다.
• 이 문제의 조건을 그대로 따라가기 위해 사용하는 시작 좌표도 (1,1) 그대로 따라가자

풀이

• 크게 2단계로 풀이 할 수 있다.

  1. (x,y) 기준점과 d1,d2 길이 정하는 모든 경우의 수를 따져서 -> “중복순열”
     • 중복순열이라 간단히 for문으로 구현할 수 있다. 본인은 재귀로 했을 뿐

  2. 경계선 방문체크와 선거구의 인원들을 구하자

     • 경계선 체크할 때 if(visited[i][j]) break; 처럼 break 해야 경계면 내부 침입X

     • 또한 2와 4선거구는 오른쪽에서 시작해줘야 경계면 침입 방지 가능해서 y-- 로 접근하자

코드

public static int N, ALL;
public static int[][] inArr = new int[24][24];
public static boolean[][] visited = new boolean[24][24];
public static int[] outArr = new int[3]; // 선택된 d1, d2
public static int x, y; // 선택된 x, y
public static int result = Integer.MAX_VALUE;

public static void solve() {
    int d1 = outArr[0]; int d2 = outArr[1];
    int cx = x; int cy = y;
    // 1.경계선 체크
    for(int i=0; i<=d1; i++) {
        visited[cx+i][cy-i] = true;
        visited[cx+d2+i][cy+d2-i] = true;
    }
    for(int i=0; i<=d2; i++) {
        visited[cx+i][cy+i] = true;
        visited[cx+d1+i][cy-d1+i] = true;
    }
    // 2.선거구 인구수 체크
    int[] people = new int[5]; // 5개구
    for(int i=1; i<cx+d1; i++) {
        for(int j=1; j<=cy; j++) {
            if(visited[i][j]) break; // break 해야 경계면 내부 침입안함
            people[0] += inArr[i][j];
        }
    }
    for(int i=1; i<=cx+d2; i++) {
        for(int j=N; j>=cy+1; j--) {
            if(visited[i][j]) break; // break 해야 경계면 내부 침입안함
            people[1] += inArr[i][j];
        }
    }
    for(int i=cx+d1; i<=N; i++) {
        for(int j=1; j<cy-d1+d2; j++) {
            if(visited[i][j]) break; // break 해야 경계면 내부 침입안함
            people[2] += inArr[i][j];
        }
    }
    for(int i=cx+d2+1; i<=N; i++) {
        for(int j=N; j>=cy-d1+d2; j--) {
            if(visited[i][j]) break; // break 해야 경계면 내부 침입안함
            people[3] += inArr[i][j];
        }
    }
    // 5번 선거구 = 전체 - 나머지 선거구
    int mod = 0;
    for(int i=0 ; i<4; i++) mod += people[i];
    people[4] = ALL - mod;

    //debug
    //System.out.println("people : "+Arrays.toString(people));

    // 3.최소값 구하기
    int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE;
    for(int i=0; i<5; i++){
        min = Math.min(min, people[i]);
        max = Math.max(max, people[i]);
    }
    result = Math.min(result, max-min);
}

public static void dfs(int depth) {
    if(depth == 2) {
        //d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N
        if(outArr[0]>=1 && outArr[1]>=1 && outArr[0]+outArr[1]+x <= N
           && 1<=y-outArr[0] && y-outArr[0] < y && y+outArr[1] <= N) {
            for(int i=0; i<=N; i++) {
                for(int j=0; j<=N; j++) {
                    visited[i][j] = false; //init
                }
            }
            solve();
            //debug
            //System.out.println(x+","+y+Arrays.toString(outArr));
        }
        return;
    }
    for(int i=1; i<=N; i++){
        outArr[depth] = i;
        dfs(depth+1);
    }
}

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    for(int i=1; i<=N; i++){
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for(int j=1; j<=N; j++){
            inArr[i][j] = Integer.parseInt(stk.nextToken());
            ALL+=inArr[i][j]; // 전체인구수 계산
        }
    }
    //run
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            x=i; y=j;
            dfs(0);
        }
    }
    //output
    System.out.println(result);
}

느낀점

생략