IT Docs

문제 링크 : www.acmicpc.net/problem/2630

스터디에서 분할 정복 문제인 백준 1780(종이의 개수)를 처음 접했다.
처음 접했을 때 문제의 흐름이나 코드 구성을 어떤 방식으로 구현해야 할지 단박에 이해됐다.
하지만 핵심 로직인 2차원 배열의 위치(1~4사분면)을 분할하는 로직을 생각해내지 못했다.
핵심 로직을 도움 없이 머릿속으로 구상하려고 하니 시간이 지날수록 머릿속은 복잡해졌다.
조금 더 여려 운 문제인 종이의 개수(Silver II)보다는 쉬운 색종이 만들기(Silver III)를 먼저 풀면서 핵심 로직을 익히기로 하였다.
등급이 조금 더 낮다고 해서 핵심 로직이 떠오르지는 않아 내가 모르는 것을 인정하고(상당히 분하지만..) 다른 분들의 코드를 보고 분석하면서 문제를 풀었다.

다음과 같이 소스를 공유합니다.

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

public class 색종이 만들기 {
    public static int N;
    public static int[][] map;
    public static int[] res = new int[2];    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++) {
               map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        divide(0, 0, N);
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < res.length; i++) {
            sb.append(res[i]).append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    public static void divide(int r, int c, int s) {
        if(checkColor(r, c, s)) {
            if(map[r][c] == 0) {
                res[0]++;
            }else {
                res[1]++;
            }
            return;
        }
        
        int ns = s/2;
        
        divide(r, c, ns);
        divide(r, c+ns, ns);
        divide(r+ns, c, ns);
        divide(r+ns, c+ns, ns);
    }
    
    public static boolean checkColor(int r, int c, int s) {
        
        int color = map[r][c];
        
        for(int i = r; i < r+s; i++) {
            for(int j = c; j < c+s; j++) {
                if(map[i][j] != color) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

핵심 로직은 divide를 재귀로 호출하는 부분이다.

divide의 파라미터를 r(row), c(col), s(size)로 받는다.

r = 0, c = 0, s = 8

예를 들면

1. 배열[0][0] ~ 배열[7][7] 까지 배열을 체크(checkColor)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

2. s(size)를 2으로 나누어 분할 한다.

3. 배열[0][0] ~ 배열[3][3] 까지 배열을 체크(checkColor)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

4. 배열[0][4] ~ 배열[3][7] 까지 배열을 체크(checkColor)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

이런식으로 전체 배열의 시작 위치와 탐색해야 하는 크기를 이용하여 1칸의 종이까지 체크할 수 있다.