문제 링크

다른 풀이에 비해서 느리지만 재귀로 구현에 성공했다는 것에 의의를 둔 풀이.

1. 종이가 모두 같은 숫자로 이뤄져있는지 확인한다.
2. 같은 숫자가 아니라면 9등분 하고 1을 반복한다.

위와 같은 형식을 가지기 때문에 재귀로 푸는게 가독성도 좋고 괜찮다. 이번 문제는 return값을 활용하지 않기 때문에 재귀적으로 이해하기보다 loop 개념으로 이해하고 풀이할 수 있었던 것 같다.

어려웠던 부분은 종이를 9등분하여 재귀를 호출하려고 할 때, 9등분된 종이 조각을 어떻게 만들것인가? 였다.

조금 지저분 하긴 하지만 index를 잘 활용해서 종이를 조각내어 배열에 저장하는데 성공했다.

// 종이 9등분해서 재귀 호출하기
for(int i = 0; i<paper.length; i+=(paper.length/3)) {
  for(int j = 0; j<paper.length; j+=(paper.length/3)) {
    int[][] piecePaper = new int[paper.length/3][paper.length/3];
    for(int k = i; k < i+paper.length/3; k++) {
      for(int l = j; l < j+paper.length/3; l++) {
        piecePaper[k-i][l-j] = paper[k][l];
      }
    }
    loop(piecePaper);
  }
}

각각 행/열의 0지점, 1/3지점 2/3지점에서 각각의 9등분된 조각을 만들어줬다. 이 부분이 핵심이었다고 생각한다.

근데 아마 재귀를 더 잘 활용했다면 저 부분도 재귀적으로 해결했을지도 모르겠다.

나의 풀이

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

public class Main {

	// 1. 종이가 모두 같은 수로 되어있으면 종이를 그대로 사용
	// 2. 1.이 아닌 경우에는 종이를 같은 코기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 1.의 과정 반복


	// 출력: -1, 0, 1 로 채워진 종이 수 출력

	static int total0 = 0;
	static int total1 = 0;
	static int totalminus1 = 0;

	static void loop(int[][] paper) {
		int count = 0;
		boolean isNotZero = false;

		for(int i =0; i<paper.length; i++) {
			for(int j = 0; j<paper.length; j++) {
				count += paper[i][j];
				if(paper[i][j] == 1 || paper[i][j] == -1) {
					isNotZero = true;
				}
			}
		}

		// 종료조건 : 종이가 모두 같은 수로 되어있음
		if(isNotZero == false  || count == paper.length*paper.length || count == -(paper.length*paper.length)) {
			if (isNotZero == false) total0 +=1;
			else if (count == paper.length*paper.length) total1 +=1;
			else if (count == -(paper.length*paper.length)) totalminus1 +=1;
			return;
		}


		for(int i = 0; i<paper.length; i+=(paper.length/3)) {
			for(int j = 0; j<paper.length; j+=(paper.length/3)) {
				int[][] piecePaper = new int[paper.length/3][paper.length/3];
				for(int k = i; k < i+paper.length/3; k++) {
					for(int l = j; l < j+paper.length/3; l++) {
						piecePaper[k-i][l-j] = paper[k][l];
					}
				}
				loop(piecePaper);
			}
		}

	}

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		int[][] paper = new int[N][N];

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

		loop(paper);

		System.out.println(totalminus1);
		System.out.println(total0);
		System.out.println(total1);

	}//main

}