[백준] 2630번 색종이 만들기 자바 (분할정복)

목차

 

 

 

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

2630번: 색종이 만들기

 

 

 

 

문제풀이

분할정복은 재귀함수를 사용하여

문제를 해결할 수 있을 때까지 하위문제로 나누어 문제를 해결하고, 결과를 다시 전체에 합치는 방법이다.

 

 

1번째는 모든 좌표를 대상으로 2중 for문을 돌려 색을 판단한다.

 => 모두 같다면 색깔에 맞게 저장

 => 하나라도 다른 색깔이 있다면 4분할

      좌측상단 : x는 0~4까지, y는 0~4까지 탐색

      좌측하단 : x는 0~4까지, y는 4~8까지 탐색

      우측상단 : x는 4~8까지, y는 0~4까지 탐색

      우측하단 : x는 4~8까지, y는 4~8까지 탐색

 

2번째는 x는 0~4까지, y는 0~4까지를 대상으로 2중 for문을 돌려 색을 판단한다.

 => 모두 같다면 색깔에 맞게 저장

 => 하나라도 다른 색깔이 있다면 4분할 ... 반복

 

 

탐색범위만 바뀔 뿐 색을 판단하는 기능은 같기때문에 colorCheck 메서드를 생성한다.

 

colorCheck메서드를 실행하여 색이 모두 같다면 white와 blue를 +1만큼 증가해야한다.

colorCheck메서드를 실행하여 색이 다르다면 좌표를 4개로 나누어야한다.

 => 색이 다르다면 반복적으로 좌표범위를 나누고

      나뉘어진 좌표범위에서 색이 같아지면, white와 blue의 개수를 전체적으로 합쳐야한다.

      따라서 재귀함수로 구현한다.

 

 

그림으로 보는 풀이

왼쪽에서 오른쪽으로 한줄씩 읽으면된다..!

colorCheck의 for-row, for-col은 주어진 x와 y의 범위를 나타낸다.

 

 

 

 

제출코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;

        board = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                 int num = Integer.parseInt(st.nextToken());
                 board[i][j] = num;
            }
        }
        //===============================
        //입력값 저장

        partition(0, 0, N);
        //색상 판단할 시작점입력
        System.out.println(white);
        System.out.println(blue);
    }

    private static void partition(int row, int col, int size) {
        //색상 모두 같은지 확인. 
        if(colorCheck(row, col, size)){	
            //색상이 모두 같다면 실행
            if(board[row][col] == 0){	
                white++;
            }else{
                blue++;
            }
            return;
        }

        //색상이 모두 같지 않다면 분할
        int newSize = size / 2;
        partition(row, col, newSize);                   //좌측상단
        partition(row, col+newSize, newSize);           //좌측하단
        partition(row+newSize, col, newSize);           //우측상단
        partition(row+newSize, col+newSize, newSize); 	//우측하단
    }

    private static boolean colorCheck(int row, int col, int size) {
        int color = board[row][col];	// 기준 Color

        for(int i = row; i < row + size; i++) {
            for(int j = col; j < col + size; j++) {
                // 색상 같지않으면 false
                if(board[i][j] != color) {
                    return false;
                }
            }
        }
        // 색상 모두 같으면 true
        return true;
    }

}