백준 코딩 2630 : 색종이 만들기

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int[][] arr = null;
    static int blueSquare = 0;
    static int whiteSquare = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int length = Integer.parseInt(br.readLine());
        arr = new int[length][length];
        for (int i = 0 ; i < length; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0 ; j < length;j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        square(0,0,length);
        System.out.println(whiteSquare);
        System.out.println(blueSquare);
        
    }
    
    static void square(int startX, int startY, int num) {
        if (num == 1) {
            if (arr[startX][startY] == 1) {
                blueSquare++;
            } else {
                whiteSquare++;
            }
            return;
        } 
        
        int sum = 0;
        for (int i = startX ; i < startX + num; i++) {
            for (int j = startY ; j < startY + num; j++) {
                sum += arr[i][j];
            }
        }
        
        if (sum == num*num) {
            blueSquare++;
        } else if (sum == 0) {
            whiteSquare++;
        } else {
            square(startX,startY,num/2);
            square(startX,startY+num/2,num/2);
            square(startX+num/2,startY,num/2);
            square(startX+num/2,startY+num/2,num/2);
        }
    }
}

설명

 

분할 정복 알고리즘을 이용하여 푸는 문제이다. 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법을 뜻한다.

그림1 8X8 종이를 보면 전체가 같은 색으로 칠해져 있지 않기 때문에 이 문제를 바로 해결할 수 없으므로 가로세로 중간을 잘라서 길이가 N/2인 정사각형 4개로 분리하여 다시 해결책을 찾는다.

 

먼저 하얀색 종이와 파란색 종이의 개수를 출력해야 하기 때문에 두 가지 값을 각각 정적 변수 blueSquare, whiteSquare로 선언한다. 그리고 색종이의 각 칸을 배열의 요소값으로 표현하기 위해 다차원 배열 int[][]를 선언한다. 그리고 값을 입력 받아 이중for문을 통해 색종이의 칸 각각의 값을 배열에 집어넣는다.

 

재귀 메소드 square(int startX, int startY, int num) 선언

 

하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복하므로 num이 1이 되는 순간 그 칸의 값이 1인지 0인지에 따라 blueSquare 혹은 whiteSquare의 값을 1증가 시킨 후 return을 한다.

 

색종이가 모두 같은 색으로 칠해져 있는지 여부를 판단하기 위해 arr[i][j]가 1일때의 모든 누적값이 해당 배열 요소의 총 개수와 일치한다면 색종이가 모두 파란색으로 칠해져 있다는 의미이므로 blueSqure값을 1 증가시키고 누적값이 0이라면 즉, 배열의 모든 요소가 0이라면 모두 흰색으로 칠해져 있다는 의미이므로 whiteSquare값을 1 증가시킨다.

 

여기까지는 바로 문제를 해결할 수 있는 경우이다. 이제 나머지 경우를 생각해봐야 하는데 나머지 경우는 바로 해결이 불가능하니 정복 알고리즘을 통한 재귀함수를 구현한다.

 

N/2 × N/2색종이로 나뉘게 되면 각각의 색종이는 왼쪽 상단을 시작으로 처음부터 끝까지 배열의 요소를 탐색해야 한다. 그러므로 4개로 나뉜 재귀 함수의 시작점과 종료점을 아래와 같이 각각 다르게 설정을 해줘야 한다.

 

            square(startX,startY,num/2);

            square(startX,startY+num/2,num/2);

            square(startX+num/2,startY,num/2);

            square(startX+num/2,startY+num/2,num/2);

 

메소드의 시작을 square(0,0,length)로 시작을 한 뒤 처음으로 4등분을 하게 되면 각각의 색종이(배열) 출발지점과 도착지점은 다음과 같다.

 

각각의 출발점과 시작점의 인덱스값을 재귀메소드의 1,2번째 매개변수로 넣고 변의 길이를 2로 나눈값을 3번째 매개변수로 넣어준다.

 

결과