[백준] code.plus(브루트 포스 Part 2,JAVA)17779번, 게리맨더링 2

문제 링크

17779번: 게리맨더링 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 기준점과 d1, d2를 이용해서 경계선을 정합니다.

2. 경계선 포함 및 안에 있는 구역은 5번 구역입니다.

3. 경계선 기준 각 구역 조건에 맞게 구역을 1~4구역을 나누었습니다.

4. 임의의 경계선을 기준으로 구역 최대 인구 - 구역 최소 인구의 차가 최소인 값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 경계선을 놓을 수 있는 모든 경우를 탐색합니다.

 

3. 모든 경우 탐색 후 최대 인구 - 최소 인구의 차의 최소값을 결과로 출력합니다.

 

경계선

 

조건(문제에서 나와있는 것을 정리한 것입니다.)

 

x + d1 + d2 <= N

x - d1 >=1

x + d2 <=N

 

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 6

1	2	3	4	1	6
7	8	9	1	4	2
2	3	4	1	1	3
6	6	6	6	9	4
9	1	9	1	9	5
1	1	1	1	9	9

 

2. 경계선을 놓을 수 있는 모든 경우를 탐색합니다.

 

※경계선을 설정하는 경우는 여러가지이지만 최소의 경우만 시뮬레이션 진행하는 것을 보여드리겠습니다.

 

경계선 : (3, 3, 1, 1)

 

1	1	1	2	2	2
1	1	1	2	2	2
1	1	5	2	2	2
3	5	5	5	2	2
3	3	5	4	4	4
3	3	4	4	4	4

전체 구역의 합 : 155

 

구역1 = 35(1 + 2 + 3 + 7 + 8 + 9 + 2 + 3)

 

구역2(최대값) = 36(4 + 1 + 6 + 1 + 4 + 2 + 1 + 1 + 3 + 9 + 4)

 

구역3(최소값) = 18(6 + 9 + 1 + 1 + 1)

 

구역4 = 35(1 + 9 + 5 + 1 + 1 + 9 + 9)

 

구역5 = 155 - (구역1 + 구역2 + 구역3 + 구역4) = 155 - 124 = 31

 

최대 인구(구역2) - 최소 인구(구역3) = 36 - 18 = 18

 

3. 모든 경우 탐색 후 득점을 가장 많이한 점수를 결과로 출력합니다.

 

최대 인구 - 최소 인구의 최소값 18을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• search함수를 경계선을 설정하는 모든 경우를 탐색합니다.
• 모든 경우를 탐색한 뒤 최대 인구-최소 인구 최소값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 4중 for문을 이용해서 경계선의 모든 경우를 만들어서 cal함수를 실행합니다.
• cal함수는 주어진 경계선 기준으로 구역들의 인구를 구해서 최대 인구 - 최소 인구를 구합니다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int N, answer = Integer.MAX_VALUE, sum = 0;
    static int[][] map;		//구역에 인구수 저장 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N+1][N+1];
        //입력값 저장 및 총 인구수 구하기
        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=N;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                sum+=map[i][j];
            }
        }
        search();	//경계선 모든 경우 탐색
        bw.write(answer + "");	//최대 인구 - 최소 인구 최소값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //경계선 만드는 모든 경우 탐색
    static void search(){
        for(int y=1;y<=N;y++)
            for(int x=1;x<=N;x++)
                for(int d1=1;d1<N;d1++)
                    for(int d2=1;d2<N;d2++)
                        if(y + d1 + d2 <= N && x-d1>=1 && x+d2<=N)	//경계선 조건
                            cal(y, x, d1, d2);
    }
    //경계선 만들어서 구역들의 인구들을 구하는 함수
    static void cal(int y, int x, int d1, int d2){
        int voteSum = 0;
        int temp = 0;

        //구역 1.
        int tempD = 1;
        for(int i=1;i<y;i++)
            for(int j=1;j<=x;j++)
                temp += map[i][j];
        for(int i=y;i<y+d1;i++) {
            for (int j=1;j<=x-tempD;j++)
                temp += map[i][j];
            tempD++;
        }
        //구역1. 비교
        voteSum += temp;
        int voteMax = temp;
        int voteMin = temp;

        //구역2.
        tempD = 1;
        temp = 0;
        for(int i=1;i<=y;i++)
            for(int j=x+1;j<=N;j++)
                temp += map[i][j];
        for(int i=y+1;i<=y+d2;i++) {
            for (int j=x+1+tempD;j<=N;j++)
                temp += map[i][j];
            tempD++;
        }

        //구역2. 비교
        voteSum += temp;
        voteMax = Math.max(voteMax, temp);
        voteMin = Math.min(voteMin, temp);

        //구역3.
        tempD = 1;
        temp = 0;
        for(int i=N;i>=y+d1+d2;i--)
            for(int j=1;j<=x+(d2-d1)-1;j++)
                temp += map[i][j];
        for(int i=y+d1+d2-1;i>=y+d1;i--) {
            for (int j=1;j<=x+(d2-d1)-1 - tempD;j++)
                temp += map[i][j];
            tempD++;
        }
        //구역3. 비교
        voteSum += temp;
        voteMax = Math.max(voteMax, temp);
        voteMin = Math.min(voteMin, temp);

        //구역4.
        tempD = 1;
        temp = 0;
        for(int i=N;i>y+d1+d2;i--)
            for(int j=x+(d2-d1);j<=N;j++)
                temp += map[i][j];
        for(int i=y+d1+d2;i>y+d2;i--) {
            for (int j=x+(d2-d1)+tempD;j<=N;j++)
                temp += map[i][j];
            tempD++;
        }
        //구역4. 비교
        voteSum += temp;
        voteMax = Math.max(voteMax, temp);
        voteMin = Math.min(voteMin, temp);

        //구역5. 구하기 및 비교
        temp = sum - voteSum;
        voteMax = Math.max(voteMax, temp);
        voteMin = Math.min(voteMin, temp);

        //최대 인구 - 최소 인구 최소값인지 비교
        answer = Math.min(answer, voteMax-voteMin);
    }
}