BJ_G4_17779_게리맨더링2

BJ_G4_17779_게리맨더링2

 

 

문제링크

http://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/g9DW3PCE_CU

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G4_17779_게리맨더링2 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    static int N;
    static int[][] popMap, areaMap;

    // 구할 값: 최소 차이
    static int MinGap = Integer.MAX_VALUE;

    // 각 영역별 인구
    static int[] pops = new int[6];

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));

        N = Integer.parseInt(input.readLine());
        popMap = new int[N][N];
        areaMap = new int[N][N];

        StringTokenizer tokens = null;
        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 0; c < N; c++) {
                popMap[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }
        /*        System.out.println("맵 확인");
        for (int[] row : popMap) {
            System.out.println(Arrays.toString(row));
        }*/

        for (int r = 1; r < N - 1; r++) {
            for (int c = 0; c < N - 2; c++) {
                // 모든 d1, d2에 대해서
                for (int d1 = 1; d1 < N; d1++) { // d1: 우상향
                    for (int d2 = 1; d2 < N; d2++) { // d2: 우하향
                        // 경계값
                        if (c + d1 + d2 < N && r - d1 >= 0 && r + d2 < N) {
                            // d1, d2에 따라 12345 구역 설정
                            for (int[] row : areaMap) {
                                Arrays.fill(row, 0);
                            }

                            mark1To4(0, r - 1, 0, c + d1, 1);
                            mark1To4(0, r - d1 + d2, c + d1 + 1, N - 1, 2);
                            mark1To4(r, N - 1, 0, c + d2 - 1, 3);
                            mark1To4(r - d1 + d2 + 1, N - 1, c + d2, N - 1, 4);

                            mark5(r, c, d1, d2);

                            /*System.out.println("결과 맵 확인: ");
                            for (int[] row : areaMap) {
                                System.out.println(Arrays.toString(row));
                            }*/
                            count();
                            Arrays.sort(pops);
                            MinGap = Math.min(MinGap, pops[5] - pops[1]);
                        }
                    }
                }
            }
        }
        System.out.println(MinGap);
    }

    static void count() {
        Arrays.fill(pops, 0);
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                pops[areaMap[r][c]] += popMap[r][c];
            }
        }
    }

    static void mark1To4(int rows, int rowe, int cols, int cole, int area) {
        for (int r = rows; r <= rowe; r++) {
            for (int c = cols; c <= cole; c++) {
                areaMap[r][c] = area;
            }
        }
    }

    // d1: 우상향, d2: 우하향
    static void mark5(int row, int col, int d1, int d2) { // 5 구역 색칠
        // 우상향2
        for (int i = 0; i <= d1; i++) {
            areaMap[row + d2 - i][col + d2 + i] = 5;
        }
        // 우하향2
        for (int i = 0; i <= d2; i++) {
            areaMap[row - d1 + i][col + d1 + i] = 5;
        }
        // 우상향 - 그리면서 오른쪽으로 5를 만날때 까지 쭉 그리기.
        for (int i = 0; i <= d1; i++) {
            areaMap[row - i][col + i] = 5;
            int right = col + i + 1;
            if (i < d1) {
                while (true) {
                    if (areaMap[row - i][right] != 5) {
                        areaMap[row - i][right] = 5;
                        right++;
                    } else {
                        break;
                    }
                }
            }
        }
        // 우하향
        for (int i = 0; i <= d2; i++) {
            areaMap[row + i][col + i] = 5;
            int right = col + i + 1;
            if (i < d2) {
                while (true) {
                    if (areaMap[row + i][right] != 5) {
                        areaMap[row + i][right] = 5;
                        right++;
                    } else {
                        break;
                    }
                }
            }
        }
    }

    private static String src = "8\r\n" +
                                "1 2 3 4 5 6 7 8\r\n" +
                                "2 3 4 5 6 7 8 9\r\n" +
                                "3 4 5 6 7 8 9 1\r\n" +
                                "4 5 6 7 8 9 1 2\r\n" +
                                "5 6 7 8 9 1 2 3\r\n" +
                                "6 7 8 9 1 2 3 4\r\n" +
                                "7 8 9 1 2 3 4 5\r\n" +
                                "8 9 1 2 3 4 5 6";
}