[백준] 1074번: Z - java

나의 풀이

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

public class Main {
	static int N, R, C, cnt;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		cut(R, C, (int) Math.pow(2, N));
	}

	private static void cut(int r, int c, int size) {
		if (size == 1) {
			System.out.println(cnt);
			return;
		}

		int half = size / 2;
		if (r < half && c < half) { // 1사분면
			cnt += half * half * 0;
			cut(r, c, half);
		} else if (r < half && c < half + half) { // 2사분면
			cnt += half * half * 1;
			cut(r, c - half, half);
		} else if (r < half + half && c < half) { // 3사분면
			cnt += half * half * 2;
			cut(r - half, c, half);
		} else if (r < half + half && c < half + half) { // 4사분면
			cnt += half * half * 3;
			cut(r - half, c - half, half);
		}
	}

}

 

 

4분할로 탐색하는 문제!

기본 아이디어는 다음과 같다.

큰 정사각형을 4개로 쪼갠 사분면에서 각각 재귀를 호출하는 것이다.

 

1사분면 탐색 ->

• 1사분면은 또다시 4개의 작은 정사각형으로 쪼개질 것이다...
  • 1사분면은 또다시 4개의 작은 정사각형으로 쪼개질 것이다...
    • .....
      • 정사각형 한 변의 크기가 1이라면 종료

2사분면 탐색 ->

• 2사분면은 또다시 4개의 작은 정사각형으로 쪼개질 것이다...
  • 2사분면은 또다시 4개의 작은 정사각형으로 쪼개질 것이다...
    • ...
      • 정사각형 한 변의 크기가 1이라면 종료

3사분면 탐색 ->

• 3사분면은 또다시 4개의 작은 정사각형으로 쪼개질 것이다...
  • 3사분면은 또다시 4개의 작은 정사각형으로 쪼개질 것이다...
    • ...
      • 정사각형 한 변의 크기가 1이라면 종료

4사분면 탐색

• 4사분면은 또다시 4개의 작은 정사각형으로 쪼개질 것이다...
  • 4사분면은 또다시 4개의 작은 정사각형으로 쪼개질 것이다...
    • ...
      • 정사각형 한 변의 크기가 1이라면 종료

이렇게 각 사분면의 정사각형 크기가 1이될 때까지 쪼개어서 Z순서로 배열을 방문하는 방법이다.

 

 

그러나 이렇게 모든 4분면을 재귀로 탐색하고, 정사각형의 size가 1이될 때까지 반복했는데 처참하게 시간초과가 났다...!

 

 

따라서 생각해본 아이디어는

=> 굳이 모든 4사분면을 탐색할 필요 없이, r행 c열에 해당하는 사분면 중 한 곳만 재귀로 탐색하는 것이다!

 

즉, N=3 이고 r=7, c=7 인 경우를 떠올려보자.

size = 8인 정사각형에서 (7,7) 좌표는 4사분면에 해당한다.

(7,7) 좌표는 행과 열이 index 4~7 에 해당하기 때문이다.

따라서 4사분면만 재귀로 탐색해야 한다.

이때 1~3사분면을 건너뛰었기 때문에 half*half*3 에 해당하는 번호를 더해주어야 한다.

그런다음, 4사분면을 (0,0) 기준으로 생각하여 다시 재귀호출을 진행한다. -> cut(r-half, c-half, half)

else if (r < half + half && c < half + half) { // 4사분면
		cnt += half * half * 3;
		cut(r - half, c - half, half);
}

 

정사각형을 쪼개다보면 더이상 쪼개지지 않는 size == 1 일 때가 존재할 것이다.

해당 경우를 기저조건으로 설정하여, 재귀문을 종료하도록 한다.

if (size == 1) {
		System.out.println(cnt);
		return;
}