백준 17779번 게리맨더링 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Gerrymandering_two {
    static int N;
    static int[][] map;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        int people=0;
        for (int i = 1; i < N+1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < N+1; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                people += map[i][j];
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < N+1; i++) {
            for (int j = 1; j < N+1; j++) {
                for (int k = 1; k < N + 1; k++) {
                    for (int l = 1; l < N + 1; l++) {
                        side(i,j,k,l,people);
                        min = Math.min(min,answer);
                    }
                }
            }
        }
        System.out.println(min);
    }
    public static void side(int x,int y,int d1, int d2,int people){
        if(x+d1+d2>N||y-d1<1||y+d2>N)
            return;
        boolean[][] visited = new boolean[N+1][N+1];
        for (int i = 0; i <= d1; i++) {
            visited[x+i][y-i] = true;
        }
        for (int i = 0; i <= d2; i++) {
            visited[x+i][y+i] = true;
        }
        for (int i = 0; i <= d2; i++) {
            visited[x+d1+i][y-d1+i] = true;
        }
        for (int i = 0; i <= d1; i++) {
            visited[x+d2+i][y+d2-i] = true;

        }
        int fir = 0;
        int sec = 0;
        int third = 0;
        int fourth = 0;
        int fifth = 0;

        for (int i = 1; i < x+d1; i++) {
            boolean flag = false;
            for (int j = 1; j <= y; j++) {
                if(visited[i][j])
                    break;
                people -= map[i][j];
                fir += map[i][j];
            }
        }
        for (int i = 1; i <= x+d2; i++) {
            boolean flag = false;
            for (int j = N; j >y; j--) {
                if(visited[i][j])
                    break;
                people -= map[i][j];
                sec += map[i][j];
            }
        }
        for (int i = x+d1; i <= N; i++) {
            boolean flag = false;
            for (int j = 1; j < y-d1+d2; j++) {
                if(visited[i][j])
                    break;
                people -= map[i][j];
                third += map[i][j];
            }
        }
        for (int i = x+d2+1; i <=N; i++) {
            boolean flag = false;
            for (int j = N; j >= y-d1+d2; j--) {
                if(visited[i][j])
                    break;
                people -= map[i][j];
                fourth += map[i][j];
            }
        }
        fifth = people;

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        max =Math.max(Math.max(Math.max(Math.max(fir,sec),third),fourth),fifth);
        min =Math.min(Math.min(Math.min(Math.min(fir,sec),third),fourth),fifth);
        answer = max - min;

    }
}

풀이방법

이 문제는 어떤 알고리즘을 쓴다기 보다는 문제에서 주는 조건에 따라 충실히 구현하는것이 핵심이다.

1. 처음 입력받으면서 총 인구수를 계산한다.

2. 4중포문을 통해 x,y,d1,d2를 완전 탐색하여 side함수에 넘겨준다.

3. 문제가 주는 조건의 범위 밖이라면 탐색하지 않는다.

4. 조건대로 경계선을 세운다.

5. 맵을 돌며 각 선거구의 인구수를 센다.(범위에 주의하자)
   이때 경계를 만나면 이후 열은 탐색하지 않는다.
   따라서 2,4구역의 열을 탐색할때는 역순으로 탐색한다.

6. 각 구역의 인구수를 총 인구수에서 빼고 남은 인구수가 5번째 선거구의 인구수가 된다.

7. 각 구역의 최대인구, 최소인구를 구하고 두 인구의 차를 answer에 담는다.

8. answer이 최소가 되는 값을 출력한다.

후기

사실 문제의 조건을 잘 따라가면 그렇게 어렵지 않은 문제였는데
5번째 선거구의 인구수를 세는부분에서 굉장히 오래걸렸다.
처음에 경계를 만나면 이후열은 5번째 선거구의 인구수에다가 추가하는 로직으로 풀었는데, 문제의 테케와, 질문게시판 테케는 전부 맞는데 채점하면 틀렸다고 나온다.(한 2시간동안 왜 안되는지 고민했는데 아직도 왜안되는지 모르겠음..)
그래서 5번째 선거구를 세는 로직을 다시 작성했고, 바로 풀렸다.
근데 처음에 내가 세운로직보다 두번째로 만든로직이 더 명확하고 조건이 덜 붙는거 같다.