[Baekjoon] 2630 - 색종이 만들기

📝 문제

 

 

🔑 풀이 과정

· 처음 풀어본 분할정복 문제

 

· 하나의 종이가 하나의 색으로 이루어져있는지 검사한다.

① 만약 하나의 색으로 이루어져 있다면, 무슨 색 종이인지 개수를 카운팅한다.

② 만약 두 가지 색이 섞여 있다면, 가로와 세로 중간을 잘라서 4개의 색종이로 나눈다. → 이 자른 4개의 색종이에도 앞서 해왔던 과정을 한다.

▶ 이를 계속 반복해서 풀이하면 되는 것. 이는 재귀적으로 표현한다.

 

· 탐색할때는 현재 색종이의 맨 위 왼쪽 위치를 기준으로 탐색할 것이다. 맨 위 왼쪽의 행 위치, 열 위치, 변 길이 3가지가 있으면 탐색이 가능하다. 

 

· 달아놓은 주석을 보면 풀이과정이 이해될 것이라 생각된다.

 

 

🔓 답안

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //입력
        int N = Integer.parseInt(br.readLine()); //전체 종이의 한 변의 길이
        board = new int[N][N]; //전체 종이

        //종이 색 입력받기
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //입력 종료

        solve(0, 0, N);

        //출력
        bw.write(white + "\n");
        bw.write(blue + "\n");
        bw.flush();
        bw.close();
    }

    static void solve(int row, int col, int size){ //메서드의 인자는 색종이 맨 왼쪽위 꼭짓점의 행번호, 열번호, 색종이의 변길이 총 3가지
        int whiteCount = 0;
        int blueCount = 0;
        for(int i = row; i < row+size; i++){ //색종이 전체탐색 하면서 색상 카운트
            for(int j = col; j < col+size; j++){
                if(board[i][j] == 0)
                    whiteCount++;
                else if(board[i][j] == 1)
                    blueCount++;
            }
        }

        if(whiteCount == (size * size)){ //색종이가 전부 하얀색으로 칠해져있으면, 하얀색 색종이 카운트 증가 후 메서드 종료
            white++;
            return;
        } else if(blueCount == (size * size)){ //색종이가 전부 파란색으로 칠해져있으면, 파란색 색종이 카운트 증가 후 메서드 종료
            blue++;
            return;
        }

        //하얀색 색종이도, 파란색 색종이도 아니면(색이 섞여있다면) 4조각으로 분할해서 다시 탐색해야함.
        int newSize = size/2;

        solve(row, col, newSize);
        solve(row, col + newSize, newSize);
        solve(row + newSize, col, newSize);
        solve(row + newSize, col + newSize, newSize);
    }

}

 

 

 

🖤 알고리즘 분류

- 분할 정복

- 재귀