[Java] 백준(실버-2) 2630번 - 색종이 만들기

문제 풀이

---

이 문제는 재귀를 이용한 분할 정복 과정을 통해 풀 수 있는 문제 중 하나이다.

아이디어 도출

문제에서 요구하는 내용은 하얀색과 파란색 정사각형 색종이의 개수이다. 그런데, 부분 색종이는 모두 같은 색으로 이루어져야 한다. 만약, 같은 색상으로 이루어진 색종이가 아닐 경우 색종이를 잘라야 한다. 이떄, 색종이를 자를 때는 절반인 1/2 씩 잘라서 새로운 색종이로 만들어야 한다.

이를 통해 생각해낸 아이디어는 다음과 같다.

1. 재귀를 통해 현재 색종이가 같은 색상으로 이루어졌는지, 다른 색상이 하나라도 있는지 확인하고, 다른 색상이 있다면 색종이를 분할한다.
2. 색종이를 분할할 때, 4등분(크기 절반)으로 분할하여 1번 과정을 반복한다.(재귀 호출)
3. 분할해낸 색종이가 모두 같은 색상으로 이루어졌다면, 해당 색상의 개수를 1 증가시키고 재귀 함수는 종료한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    static int[][] arr;
    static int w, b;

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

        // 첫째줄에는 하얀색 색종이(0)의 개수, 둘째줄에는 파란 색종이(1)의 개수를 출력

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

        arr = new int[N][N];

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 하얀색, 파란색 색종이의 개수를 세기 위해 0으로 초기화
        w = 0;
        b = 0;

        recursion(0, 0, N);
        
        bw.write(w+"\n");
        bw.write(b+"\n");
        
        bw.close();
        br.close();
    }

    static void recursion(int r, int c, int size) {

        // 1. 현재 파티션의 색종이가 모두 같은 색으로 이루어졌다면 개수를 1 증가시키고 함수를 종료한다.
        if(isEquals(r, c, size)) {
            
            if(arr[r][c] == 0) {
                w++;
            } else {
                b++;
            }

            return;
        }

        // 2. 만약 현재 파티션이 다른 색으로 이루어졌다면, 4등분한 후 다시 확인한다.
        int newSize = size / 2 ;
        recursion(r, c, newSize);
        recursion(r+newSize, c, newSize);
        recursion(r, c+newSize, newSize);
        recursion(r+newSize, c+newSize, newSize);

    }

    static boolean isEquals(int r, int c, int size) {
        
        // 색종이의 첫번째 원소
        int color = arr[r][c];

        // 해당 파티션을 순회하면서 같은 색 여부를 확인하여 결과 반환
        for(int i=r; i<r+size; i++) {
            for(int j=c; j<c+size; j++) {
                if(arr[i][j] != color) {
                    return false;
                }
            }
        }
        
        // 같은 색이라면 true 반환
        return true;
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.