[BOJ] 17779 게리맨더링 2 -Java

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

17779번: 게리맨더링 2

[풀이]

시간 제한 1초에 총 1억번 연산이다.

여기서 N은 20까지, 우리가 정해야 할 것은 1<=r,c,d1,d2<=20이다.

=> O(N^4) =  160,000 => 삽가능이다.

(왜 4중 for문은 안된다고만 생각했을까.. 왜 다른 범위 조건을 내가 찾아야 한다고 생각했을까.. 시간복잡도 볼껄..)

 

0. 문제에서 x는 row이고, y는 col이다. (헷갈려서 몇 번 엎었다.)

 

1. 우선 좌표 중에서 어느 점을 기준점으로 할 것인지, d1과 d2를 어떻게 설정할 것인지를 정해야 한다.

4중for문으로 구하고, 범위에 해당하는지로 가능한지를 살핀다.

 (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

//r,c쌍
for(int r=1;r<=N;r++) {
   for(int c=1;c<=N;c++) {
      //d1,d2찾기
      for(int d1=1;d1<=N;d1++) {
         for(int d2=1;d2<=N;d2++) {
            if(r+d1+d2<=N && 1<=c-d1 && c<c+d2 && c+d2<=N){
               //여기서 각 지역의 인구수 구하기
               int small = getSmall(r,c,d1,d2);
               answer = Math.min(answer,small);
            }
         }
      }
   }
}

2. r,c,d1,d2가 정해졌으면 해당 부분에서 각 지역의 인구수들을 확인해야 한다.

경계선은 다음과 같다. 

1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

선거구의 범위는 다음과 같다.

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

1번 선거구는 위의 범위에서, 5번에 해당하지 않는 부분이다. 2,3,4번도 마찬가지.

근데 5번 선거구 안쪽의 범위를 확정하는 것은 매우 어렵다. (이걸 정해보려고 하다가 N시간을 날렸다... 흑..)

그러므로 경계선을 그려놓고, 이 경계선 전까지를 각 구의 범위로 확정하자. (1,3번은 왼쪽에서부터, 2,4번은 오른쪽에서부터 시작한다.)

 

3. 각 선거구의 인원을 HashMap에 넣어두고, 모든 좌표를 다 돌았으면 ArrayList에 넣고 인원수로 정렬한다.

5번선거구는 구하기 어려우므로 총 인원수(total)에서 1,2,3,4의 인원수를 빼서 구한다.

 

4. 절댓값 중 가장 작은 것을 구하면 끝

 

[코드]

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

public class Main {
   static StringTokenizer st;
   static int N;
   static int[][] Map;
   static int answer = Integer.MAX_VALUE;
   static int total = 0;
   
   public static void main(String[] args) throws Exception{
      // TODO Auto-generated method stub
      //System.setIn(new FileInputStream("src/main/java/input.txt"));
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      Map = new int[N+1][N+1];
      
      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());
            total += Map[i][j];
         }
      }
      
      //r,c쌍
      for(int r=1;r<=N;r++) {
         for(int c=1;c<=N;c++) {
            //d1,d2찾기
            for(int d1=1;d1<=N;d1++) {
               for(int d2=1;d2<=N;d2++) {
                  if(r+d1+d2<=N && 1<=c-d1 && c<c+d2 && c+d2<=N){
                     //여기서 각 지역의 인구수 구하기
                     int small = getSmall(r,c,d1,d2);
                     answer = Math.min(answer,small);
                  }
               }
            }
         }
      }
      
      System.out.println(answer);
   }
   
   static int getSmall(int row, int col, int d1, int d2) {
      HashMap<Integer,Integer> hashMap = new HashMap<>();

      //경계 설정
      boolean[][] visit = new boolean[N+1][N+1];
      for(int i=0;i<=d1;i++){
         visit[row+i][col-i] = true;
         visit[row+d2+i][col+d2-i] = true;
      }
      for(int i=0;i<=d2;i++){
         visit[row+i][col+i] = true;
         visit[row+d1+i][col-d1+i] = true;
      }


      for(int i=1;i<row+d1;i++){
         for(int j=1;j<=col;j++){
            if(visit[i][j]){
               break;
            }
            if(hashMap.containsKey(1)) {
               hashMap.put(1, hashMap.get(1)+Map[i][j]);
            }
            else {
               hashMap.put(1, Map[i][j]);
            }
         }
      }
      for(int i=1;i<=row+d2;i++){
         for(int j=N;j>col;j--){
            if(visit[i][j]){
               break;
            }
            if(hashMap.containsKey(2)) {
               hashMap.put(2, hashMap.get(2)+Map[i][j]);
            }
            else {
               hashMap.put(2, Map[i][j]);
            }

         }
      }
      for(int i=row+d1;i<=N;i++){
         for(int j=1;j<col-d1+d2;j++){
            if(visit[i][j]){
               break;
            }
            if(hashMap.containsKey(3)) {
               hashMap.put(3, hashMap.get(3)+Map[i][j]);
            }
            else {
               hashMap.put(3, Map[i][j]);
            }

         }
      }
      for(int i=row+d2+1;i<=N;i++){
         for(int j=N;j>=col-d1+d2;j--){
            if(visit[i][j]){
               break;
            }
            if(hashMap.containsKey(4)) {
               hashMap.put(4, hashMap.get(4)+Map[i][j]);
            }
            else {
               hashMap.put(4, Map[i][j]);
            }
         }
      }

      ArrayList<Point> Arr = new ArrayList<>();
      int oneToFour = 0; //5구역 = total - 1~4합(oneToFour)
      for(int key:hashMap.keySet()) {
         Arr.add(new Point(key,hashMap.get(key)));
         oneToFour += hashMap.get(key);
      }
      Arr.add(new Point(5,total - oneToFour));
      Collections.sort(Arr); //합 순으로 정렬

      return Math.abs(Arr.get(Arr.size()-1).num - Arr.get(0).num);
   }

   static class Point implements Comparable<Point>{
      int district;
      int num;

      public Point(int district, int num) {
         super();
         this.district = district;
         this.num = num;
      }
      @Override
      public int compareTo(Point o) {
         return Integer.compare(num, o.num);
      }
   }
}

[느낀점]

소요시간 : 6h...

나는 왜이리 어려웠을까, 왜 다른 범위를 내가 정해줘야 한다. 규칙을 찾아야 한다 라고 생각했을까

범위를 다 주어줬는데 ㅜㅜ 

그리고 앞에서부터 생각하는거 말고도, 뒤에서부터 생각하는 것도 머리에 넣어 두자

추가로 시간복잡도 꼭 고려해보자!!