[java]색종이 만들기 - 백준2630

문제

• 색종이 만들기(백준2630)

풀이

문제 해석을 하자면,

• 입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.
• 잘라지는 크기가 동일하게 잘라지므로 (1/2로 잘라짐) “분할정복” 문제

풀이

• “좌상, 우상, 좌하, 우하” 4가지로 재귀를 구현했다.
• 특히 매개변수로 “시작좌표 와 크기” 를 넘겨줌으로써 간단히 구현했다.
  • 크기를 넘겨줌으로써 끝좌표는 “시작좌표+크기” 로 간단히 구하는게 아이디어

코드

static int[][] inArr = new int[130][130];
static int white, blue, N;

static void paper(int cx, int cy, int size) {
    //base condition
    if(size <= 0) return;
    if(size == 1) {
        if(inArr[cx][cy]==0) white++;
        if(inArr[cx][cy]==1) blue++;
        return;
    }
    int first = inArr[cx][cy];
    boolean success = true;
    loop:for(int i=0; i<size; i++){
        for(int j=0; j<size; j++) {
            int second = inArr[cx+i][cy+j];
            if(first != second) {
                success=false;
                break loop;
            }
        }
    }
    if(success){
        if(first==0) white++;
        if(first==1) blue++;
        return;
    }// 여기까지가 base condition

    //debug
    //    for(int i=cx; i<cx+size; i++){
    //      System.out.println(Arrays.toString(Arrays.copyOfRange(inArr[i],cy,cy+size)));
    //    }
    //    System.out.println(size+"크기");

    //recursion
    int half = size/2;
    paper(cx,cy,half); //좌상
    paper(cx,cy+half,half); //우상
    paper(cx+half,cy,half); //좌하
    paper(cx+half,cy+half,half); //우하
}

public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    for(int i=0; i<N; i++){
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++){
            inArr[i][j] = Integer.parseInt(stk.nextToken());
        }
    }
    paper(0,0,N); //좌표와 크기
    System.out.println(white);
    System.out.println(blue);
}

느낀점

debug를 잘 찍어야 구현하기 쉽다.