알고리즘35 :: BOJ_17779_게리맨더링2

 

꽥님의 오픈프로필

 

게리맨더링2는 좌우 대각선으로 늘어나는 방법과 밑으로 모이는 지점만 잘 체크해서 빡구현 하면된다.

구역이 총 5구역이 있으므로 전체 맵에 값을 계산하는 total 값이 있으면 좋다.

그리고 구역을 나누고 값을 설정해두면 더 좋다. 헷갈리는 일이 없다. 

1 1 1 5 2 2

1 1 5 5 2 2

1 5 5 5 3 3

... 

이런식으로 표시해두면 나중에 값을 계산할때 불편하지 않았다. 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    private static int n, rx, ry, lx, ly, cx, cy, srx, sry, slx, sly;
    
    private static int[][] map;
    private static int ans = Integer.MAX_VALUE;
    private static int[] sum;
    private static int f;
    private static int[][] visit;
    private static class Pair{
        int x;
        int y;
        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    private static ArrayList<Pair> a,a2;
    private static ArrayList<Pair> b,b2;
    private static int Calc(int x, int y) {
        //root : x,y
        //left : slx, sly
        //right : srx, sry
        //cross point : a.get(a.size()-1).x, a.get(a.size()-1).y
        
        //x = 2, y = 4, d1 = 2, d2 = 2
        int c = 0;
        for(int i=0; i<slx; i++) {
            for(int j=0; j<=y; j++) {
                //1 ≤ r < x+d1, 1 ≤ c ≤ y
                if(visit[i][j] == 0) {
                    sum[0] += map[i][j];
                    visit[i][j] = 9;
                }else
                    break ;
            }
        }//1선거구 종료
        c+=sum[0];
        for(int i=0; i<=srx; i++) {
            for(int j=n-1; j>y; j--) {
            //1 ≤ r ≤ x+d2, y < c ≤ N
            if(visit[i][j] == 0) {
                sum[1] += map[i][j];
                visit[i][j] = 2;
            }else
                break ;
            }
        }//2선거구 종료
        
        c+=sum[1];
        for(int i=slx; i<n; i++) {
            for(int j=0; j<a.get(a.size()-1).y; j++) {
                // x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
                if(visit[i][j] ==0) {
                    sum[2] +=map[i][j];
                    visit[i][j] = 3;
                }else
                    break ;
            }
        }//3선거구 종료
        
        c+=sum[2];
        for(int i=srx+1; i<n; i++) {
            for(int j=n-1; j>a.get(a.size()-1).y-1; j--) {
                if(visit[i][j] == 0) {
                    sum[3] += map[i][j];
                    visit[i][j] = 4;
                }else
                    break ;
            }
        }//4선거구 종료
        c+=sum[3];
        
        sum[4]= f-c;
        Arrays.sort(sum);
        return sum[sum.length-1]-sum[0];
        
    }
    private static void DFS(int nn) {
        int x = nn/n;
        int y = nn%n;
        if(nn>=(n-1)*n+(n-1)) return ;
 
        
        lx = x;
        ly = y;
        a2 = new ArrayList<>();
        a2.add(new Pair(x,y));
        boolean move = false;
        while(true) {
            rx = x;
            ry = y;
            
            a = new ArrayList<>();
            a.add(new Pair(x,y)); // 가장 root 
            //왼쪽 고정 = 왼쪽 대각선 y 1 감소 x 1 증가 
            lx +=1;
            ly -=1;
            a2.add(new Pair(lx,ly));
            if(lx>=n || lx<0 || ly>=n || ly<0) {
                lx -=1; ly+=1;
                break; //더이상 갈 수 없으므로 볼 필요가 없음 
            }
            //왼쪽 점 
            a.add(new Pair(lx,ly));
            slx =lx; sly=ly;
            
            //오른쪽 이동 
            
            while(true) {
            
                //오른쪽  = 오른쪽 대각선 y 1 증가 x 증가 
                rx+=1;
                ry+=1;
                if(rx>=n || rx<0 || ry>=n || ry<0) {
                    rx-=1;    ry-=1;
                
                    break;
                }
                
                //오른쪽 점
                a.add(new Pair(rx,ry));
                srx = rx; sry = ry;
                
                visit = new int[n][n];
                //모여서 만나는 구간
                int tlx = lx;
                int tly = ly;
                int trx = rx;
                int ttry = ry;
                
                b = new ArrayList<>();
                b2 = new ArrayList<>();
                boolean f1=true;
                boolean f2=true;
                boolean f3=false;
                while(f1 || f2) {
                    //왼쪽 내리자
                    lx+=1;
                    ly+=1;
                    
                    if(lx>=n || lx<0 || ly>=n || ly<0) {
                        //break; //더이상 갈 수 없으므로 볼 필요가 없음 
                        f1 = false;
                    }
                    
                    if(f1!=false && visit[lx][ly]==1) {
                        cx = lx; cy = ly;
                        //교차점 
                        a.add(new Pair(cx,cy));
                        visit[b2.get(b2.size()-1).x][b2.get(b2.size()-1).y]=0;
                        f3=true;
                        break ;
                    }else if(f1!=false){
                        visit[lx][ly] = 1;
                        b.add(new Pair(lx,ly));
                    }
                    
                    //오른쪽 내리자 
                    rx+=1;
                    ry-=1;
                    
                    if(rx>=n || rx<0 || ry>=n || ry<0) {
                        f2 = false;
                    }
                    
                    if(f2!= false && visit[rx][ry]==1) {
                        cx=rx; cy=ry;
                        //교차점
                        a.add(new Pair(cx,cy));
                        visit[b.get(b.size()-1).x][b.get(b.size()-1).y]=0;
                        f3=true;
                        break;
                    }else if(f2!=false){
                        visit[rx][ry] = 1;    
                        b2.add(new Pair(rx,ry));
                    }
                    
                }
                if(f3==true) {
                for(int i=0; i<a.size(); i++)
                    visit[a.get(i).x][a.get(i).y] = 1;
                
                for(int i=0; i<a2.size(); i++) {
                    if(visit[a2.get(i).x][a2.get(i).y]!=1)
                        visit[a2.get(i).x][a2.get(i).y] = 1;
                }
                
                //좌표값을 visit에 true 
                
                sum = new int[5];
                int t = Calc(x, y); //선거구별 값 계산, root 값만 넘겨줌
                
                a.remove(a.size()-1); //교차점 삭제 
                
                if(t != Integer.MAX_VALUE && ans>t) {
                    if(t==13) {
                        System.out.println("x" + x +" "+"y"+y);
                    }
                    ans = t;
                }
                
                lx = tlx;
                ly = tly;
                rx = trx;
                ry = ttry;
                }
            }
        }
        
        DFS(nn+1);
 
    }
    
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                f+=map[i][j];
            }
        }//end of for loop
        
        
        
        DFS(0);
        System.out.println(ans);
        
        
    }
 
}
 
 

잘짠 코드는 절대 아니다.

더 효율적인 코드가 많다. 

시뮬레이션이라 크게 생각하지 않고 조건에 맞게 구성해줬다.