[백준] 2630번 : 색종이 만들기 - 자바[Java]

2630번: 색종이 만들기

풀이

재귀함수를 이용한 분할정복을 사용하여 문제를 풀 수 있다.

 

main 함수에서 전체 종이의 한 변의 길이 N과 색종이의 위치 정보를 입력받고

divideAndConquer() 재귀 함수를 호출하여 (0, 0)부터 색종이 배열 탐색을 시작한다.

divideAndConquer() 함수 내에서 인자로 받은 시작위치부터 색종이 배열을 탐색하다가, 시작 위치의 색과 다른 색을 발견하면 위 그림과 같이 색종이를 4등분하여 새로운 탐색을 시작해야 한다. 즉, 다음과 같이 4번의 재귀함수를 호출하고, 현재 진행중인 탐색은 계속할 필요가 없으므로 바로 return 한다.

// n은 현재 탐색하는 색종이의 크기, papers는 색종이 배열, x, y는 현재 탐색 시작 위치
static void divideAndConquer(int n, int[][] papers, int x, int y) {
        int startColor = papers[x][y];
        
        ...

        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (papers[i][j] != startColor) {
                    divideAndConquer(n / 2, papers, x, y);
                    divideAndConquer(n / 2, papers, x + n / 2, y);
                    divideAndConquer(n / 2, papers, x, y + n / 2);
                    divideAndConquer(n / 2, papers, x + n / 2, y + n / 2);
                    return;
                }
            }
        }
        
        ...
    }

만약 n이 1이거나, 인자로 주어진 n*n 크기만큼 배열을 모두 탐색했는데도 전부 같은 색이라면, 하얀색 색종이 또는 파란색 색종이의 개수를 업데이트한다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int whitePapers = 0;
    static int bluePapers = 0;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] papers = new int[n][n];

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

        divideAndConquer(n, papers, 0, 0);
        
        System.out.println(whitePapers);
        System.out.println(bluePapers);

    }

    static void divideAndConquer(int n, int[][] papers, int x, int y) {
        int startColor = papers[x][y];

        if (n == 1) {
            if (startColor == 1)
                bluePapers++;
            else
                whitePapers++;
            return;
        }

        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (papers[i][j] != startColor) {
                    divideAndConquer(n / 2, papers, x, y);
                    divideAndConquer(n / 2, papers, x + n / 2, y);
                    divideAndConquer(n / 2, papers, x, y + n / 2);
                    divideAndConquer(n / 2, papers, x + n / 2, y + n / 2);
                    return;
                }
            }
        }

        if (startColor == 1)
            bluePapers++;
        else
            whitePapers++;
    }
}