[BOJ 분할정복] 종이의 개수 1780.JAVA

문제 링크 : https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

---

종이의 개수 문제를 접했을 때 분할 하는 방법을 몰랐다.

그래서 아래의 색종이 만들기 문제를 먼저 풀면서 분할 정복의 핵심 로직을 익혔다.

두 문제를 다 풀어보니 둘중 뭐가 더 어렵다고 말하기 힘들정도로 비슷하다.

종이의 개수 문제가 분할의 범위가 커졌을뿐이다.

그래도 분할의 범위가 작은 색종이 만들기 부터 풀고나니 종이의 개수 문제를 대하는 태도가 달라졌다.

난이도 낮은 문제를 푼게 아주 큰 도움이 되었다.

nkt-docs.tistory.com/21

[BOJ 분할정복] 색종이 만들기 2630.JAVA

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

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

public class 종이의 개수 {
    public static int N;
    public static int[][] map;
    public static int[] res = new int[3];
    public static void main(String[] arsg) 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();
        
        sb.append(res[2]).append("\n");
        sb.append(res[0]).append("\n");
        sb.append(res[1]).append("\n");
        
        System.out.println(sb.toString());
    }
    
    public static void divide(int r, int c, int s) {
        if(checkNum(r, c, s)) {
            int num = map[r][c];
            if(num == -1) {
                res[2]++;
            }else {
                res[num]++;
            }
            return;
        }
        
        int ns = s/3;
        
        divide(r, c, ns);
        
        divide(r, c+ns, ns);
        divide(r, c+ns*2, ns);
        
        divide(r+ns, c, ns);
        divide(r+ns*2, c, ns);
        
        divide(r+ns, c+ns, ns);
        
        divide(r+ns, c+ns*2, ns);
        divide(r+ns*2, c+ns, ns);        
        
        divide(r+ns*2, c+ns*2, ns);
    }
    
    public static boolean checkNum(int r, int c, int s) {
        int num = map[r][c];
        
        for(int i = r; i < r+s; i++) {
            for(int j = c; j < c+s; j++) {
                if(map[i][j] != num) return false;
            }
        }
        
        return true;
    }
}

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

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

r = 0, c = 0, s = 9

예를 들면

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

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

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

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

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

 

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