문제 출처

단계별로 풀어보기 > 분할 정복 > 색종이 만들기
https://www.acmicpc.net/problem/2630

문제 설명

접근 방법

구간 별로 색종이 색이 같은지 판별하는 재귀 함수 quarter을 실행한다. 이 때, 같은 색이 아니라면 해당 구간(x축, y축)을 2분의 1 한 구간을 다시 quarter를 실행하여 종이의 색이 같을 때까지 반복한다.

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

public class 색종이_만들기 {
    static int white = 0;
    static int blue = 0;
    static int[][] paper;

    public static void quarter(int startx, int starty, int endx, int endy){
        int color = paper[startx][starty];
        boolean check = true;
        // 색종이가 같은 색인지 판별
            for(int i = startx; i<endx; i++){
                for(int j = starty; j<endy; j++){
                    if(paper[i][j] != color){
                        check = false;
                        break;
                    }
                    if(!check) break;
                }
            }

            if(check){
                if(color == 0) white++;
                else blue++;
                return;
            }

                int nextx = (endx+startx)/2;
                int nexty = (endy+starty)/2;
                quarter(startx,starty,nextx,nexty);
                quarter(nextx,starty,endx,nexty);
                quarter(startx,nexty,nextx,endy);
                quarter(nextx,nexty,endx,endy);

        }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        paper = new int[N][N];

        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<N; j++){
                int check = Integer.parseInt(st.nextToken());
                paper[i][j] = check;
            }
        }
        quarter(0,0,N,N);
        bw.write(white + "\n");
        bw.write(blue + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

Review

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

public class 색종이_만들기_review {

    static int white = 0;
    static int blue = 0;
    static int[][] paper;

    public static void quarter(int startx, int endx, int starty, int endy){
        int start = paper[startx][starty];
        boolean check = true;
        for(int i = startx; i<endx; i++){
            for(int j = starty; j<endy; j++){
                if(paper[i][j] != start){
                    check = false;
                    break;
                }
            }
            if(!check) break;
        }

        if(check){
            if(start == 0){
                white++;
                return;
            }else{
                blue++;
                return;
            }
        }

        int nextx = (endx + startx) / 2;
        int nexty = (endy + starty) / 2;

        quarter(startx,nextx,starty,nexty);
        quarter(startx,nextx,nexty,endy);
        quarter(nextx,endx,starty,nexty);
        quarter(nextx,endx,nexty,endy);
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        paper = new int[N][N];
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<N; j++){
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        quarter(0,N,0,N);

        bw.write(white+"\n");
        bw.write(blue+"\n");
        bw.flush();
        bw.close();
        br.close();


    }
}

알게된 점

문제푼 흔적

Review