관련글
분할정복 관련 포스팅은 여기를 참조
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);
}
}
}
}
읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.