알고리즘 풀이 - 백준 1780(종이의 개수, 분할정복)

 

관련글

 

분할정복 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

 

NxN 크기의 행렬에 각 칸에 -1, 0, 1이 저장되어 있을 때, 다음의 규칙으로 자르고 같은 수로 이루어진 종이일 때, 그 결과를 찾는 문제

① 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
② (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

 

 

2. 풀이

 

이 문제는 고려할 부분이 총 3가지이다.

① 종이를 9등분하여 분할하는 방법
② 현재 종이에 입력된 값이 동일한지 확인하는 방법
③ 그 결과를 저장하는 방법

 

문제에서 보다 시피, 현재 종이 상태에서 같은 숫자가 모두 써져 있는지를 계속 확인해야 한다. 주어지는 N의 값은 $3^k) 꼴이므로 무조건 가로/세로를 3등분을 할 수 있다.

즉, 전체 종이를 현재 종이가 1x1이 될 때까지 9등분을 할 수 있고, 현재 종이에 적힌 숫자가 같을 때까지 분할 후 확인하면 되는 문제이다.

 

우선, ②와 ③은 반복문과 변수를 통해 간단히 해결할 수 있다. 9등분을 어떻게 할까?

 

간단히 위 그림을 보자. 현재 N의 값은 9일 것이다.(길이가 9)

그러면, 행렬을 구분할 때, 행과 열이 각각 0, 3, 6으로 시작하여 구분되는 것을 알 수 있다.

이 값은 9를 3으로 나눈 것을 0, 1, 2에 곱한 값과 같다. 이 원리를 이용해 행렬을 9등분하는 작업을 지속 반복할 수 있다.

 

그러면 코드를 통해 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        int[] ans = new int[3];

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

        // 분할정복 시작하여 종이의 값을 입력받는다.
        divide(arr, ans, 0, 0, n);
        StringBuilder sb = new StringBuilder();
        sb.append(ans[0]).append("\n").append(ans[1]).append("\n").append(ans[2]);
        System.out.println(sb);
        br.close();
    }
    
    // 현재 종이의 행렬 부분에 대해 같은 숫자로 이루어져 있는지 확인하는 메소드
    private static boolean same(int[][] arr, int y, int x, int n){
        for(int i=y; i < y+n; i++){
            for(int j=x; j < x+n; j++){
                if(arr[y][x] != arr[i][j]) return false;
            }
        }
        return true;
    }

    // 매개변수 내역
    /*
      int[][] arr : 전체 배열
      int[] ans : -1, 0, 1의 숫자로 이루어진 종이 수 결과값을 저장하는 배열(index는 0부터이므로 +1씩해서 저장)
      int y : 현재 등분된 종이의 Row 시작 위치
      int x : 현재 등분된 종이의 Col 시작 위치
      int n : N 값( 계속 3으로 나누어서 전달)
    */
    
    // 종이를 9등분하고 현재 등분된 종이가 같은 숫자로만 이루어진 경우 그 결과를 저장
    // 같은 숫자로 이루어진 종이를 찾을 때까지 반복(혹은 1x1만 남을 때까지)
    private static void divide(int[][] arr, int[] ans, int y, int x, int n){

        if(same(arr, y, x, n)){
            ans[arr[y][x]+1]++;
            return;
        }
        int m = n/3;
        for(int i=0; i < 3; i++){
            for(int j=0; j < 3; j++) {
                divide(arr, ans, y+i*m, x+j*m, m);
            }
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.