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

[ 백준 17779 ] 게리맨더링 2 (자바)

 

삼성 2019 하반기 오전 첫 번째 문제 

시뮬 문제 (+ dfs, +간혹 dp로 푸는 사람들도 있는 듯 )

문제에 조건들이 많아지고 복잡해지고 있다. 

 

 

출처:백준 https://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

 

 

 

 

핵심 

• y, x입력 주의
  입력에 대해서 y, x가 다른 문제들과 다르게 반대로 다루고 있다.
  또한, 가능하면 문제의 조건을 따르는 형태의? 변수 사용 
  
  
• 경계 주의 
  5구역을 나눠서 다뤄야 하기 때문에 조건들이 다소 까다롭다. 이상, 이하, 초과, 미만.. 
  
  
• 초기화 
  재사용할 배열은 제대로 초기화하기 
  
  
• TC
  최소인 경우, 최소에서 약간 벗어난 경우 모두 시도
• 5구역의 경계 내부 설정하기 
  우선, 5구역의 경계를 모두 표시한다. 5구역은 마름모 모양으로 구성되어있는데, 마름모에 / \ 이 경계 바로 아랫부분에서 dfs를 시작한다. dfs는 5가 아닌 모든 구역을 5로 표시한다. 

 

구조

for( 모든 x )

    for( 모든 y ) 

       for ( 모든 d1, 1 ~ 2N )

           for( 모든 d2, 1 ~ 2N )

               if ( y, x, d1, d2의 범위 만족 ) 

                   1구역 색칠()

                  2구역 색칠()

                  3구역 색칠()

                  4구역 색칠()

                  5구역 색칠()

                 구역의 최대, 최소사용하여 답 만들기 

 

1, 2, 3, 4 구역은 조건대로 색칠()

5구역 색칠()

    5구역 경계 색칠 -> 한 변을 루프 하나로 만들기 

    위에 경계 /\ 에서 x축으로 +1 만큼의 자리에서 dfs 시작.

    -> 여기서 시간이 조금 걸렸다. 그냥 중심점 x에서 +1 위치에서만 dfs 하면 된다고 생각했다. 

    dfs는 5가 아닌 곳을 방문하여 5로 바꾸고 다시 5가 아닌 곳을 방문한다. 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static int[][] people, election;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        people = new int[N+1][N+1];
        election = new int[N+1][N+1];
        
        StringTokenizer st;
        for(int i = 1 ; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1 ; j <= N ; j++) {
                people[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int x = 1 ; x <= N; x++) {
            for(int y = 1 ; y <= N ; y++) {
                // 모든 d1, d2에 대해서 
                for(int d1 = 1 ; d1 < N*2 ; d1++) {
                    for(int d2 = 1 ; d2 < N * 2 ; d2++) {
                        
                        if(x + d1 + d2 <= N && 1 <= y-d1 && y+d2 <= N) {
                            // d1, d2에 따라 12345 구역 설정 
                            select1(x, y, d1, d2);
                            select2(x, y, d1, d2);
                            select3(x, y, d1, d2);
                            select4(x, y, d1, d2);
                            select5(x, y, d1, d2);
                            
                            // 구역 최대, 최소 개수 세기 
                            count();
                        }
                    }
                }
            }
        }
        System.out.println(ans);
        
    }
    static void select1(int x, int y, int d1, int d2) { // 1 구역 색칠 
        for(int r = 1; r < x + d1; r++) {
            for(int c = 1 ; c <= y; c++) {
                election[r][c] = 1;
            }
        }
    }
    static void select2(int x, int y, int d1, int d2) { // 2 구역 색칠 
        for(int r = 1; r <= x + d2 ; r++) {
            for(int c = y+1 ; c <= N ; c++) {
                election[r][c] = 2;
            }
        }
    }
    static void select3(int x, int y, int d1, int d2) { // 3 구역 색칠 
        for(int r = x+d1; r <= N; r++) {
            for(int c = 1 ; c < y-d1+d2 ; c++) {
                election[r][c] = 3;
            }
        }
    }
    static void select4(int x, int y, int d1, int d2) { // 4 구역 색칠 
        for(int r = x+d2+1; r <= N ; r++) {
            for(int c = y-d1+d2 ; c <= N; c++) {
                election[r][c] = 4;
            }
        }
    }
    
    static void select5(int x, int y, int d1, int d2) { // 5 구역 색칠 
        
        // 경계 색칠 
        for(int alpha = 0 ; alpha <= d1; alpha++) {
            election[x+alpha][y-alpha] = 5;
        }
        for(int alpha = 0 ; alpha <= d2; alpha++) {
            election[x+alpha][y+alpha] = 5;
        }
        for(int alpha = 0 ; alpha <= d2; alpha++) {
            election[x+d1+alpha][y-d1+alpha] = 5;
        }
        for(int alpha = 0 ; alpha <= d1; alpha++) {
            election[x+d2+alpha][y+d2-alpha] = 5;
        }
        
        // 내부 색칠, 마름모 모양이기 때문에 마지막 끝은 제외.
        for(int alpha = 0 ; alpha < d1; alpha++) {
            inner5(x+alpha+1, y-alpha);
        }
        for(int alpha = 0 ; alpha < d2; alpha++) {
            inner5(x+alpha+1, y+alpha);
        }
        
    }
    
    static int[][] delta = {
            {-1, 0},
            {1, 0},
            {0, 1},
            {0, -1}
    };
    // 5구역 내부 
    static void inner5(int x, int y) {
        election[x][y] = 5;
        
        int ny, nx;
        for(int dir = 0 ; dir < 4; dir++) {
            nx = x + delta[dir][1];
            ny = y + delta[dir][0];
            if(ny > 0 && ny <= N && nx > 0 && nx <= N && election[nx][ny] != 5) {
                inner5(nx, ny);
            }
        }
    }
    
    static int ans = 987654321;
// 구역 수를 세고, 최대 최소를 이용하여 답 구한다.
    static void count() {
        
        // counts[i]: i번 구역의 인구 수 
        int[] counts = new int[6];
        for(int r = 1 ; r <= N; r++) {
            for(int c= 1 ; c<= N; c++) {
                counts[election[r][c]] += people[r][c];
                people[r][c] = 1;
            }
        }
        
        int min = 987654321, max = -1;
        for(int i = 1 ; i <= 5 ; i++) {
            if(min > counts[i]) {
                min = counts[i];
            }
            if(max < counts[i]) {
                max = counts[i];
            }
        }
        if( ans > max - min) {
            ans = max- min;
        }
    }
}