[백준] Z_1074번 - 공룡 루디

 Z_1074 solved.ac 실버 1

https://www.acmicpc.net/problem/1074

1074번: Z

 

 문제 해석 및 풀이

 

Z 문제는

2차원 배열이 주어졌을 때

Z탐색을 진행하고 탐색을 진행할 때 주어진

r 행과 c열을 몇 번째로 방문하느냐를 구하는 문제입니다.

 

Z탐색을 구현하려고 하면 구현할 수 있겠지만

행과 열의 크기는 최대 2^15으로 32768입니다.

이렇게 되면 2차원 배열의 최대 크기는 32768*32768로

1073741824 약 10억을 넘는 크기가 됩니다.

 

하지만 주어진 제한 시간은 0.5초로 단순하게 Z탐색을 하면

시간 초과가 나올 확률이 엄청 큽니다.

 

이 문제는 Z 탐색의 특성을 보면 4 부분으로 쪼갤 수 있다는 점입니다.

편의상 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 1,2,3,4 분면이라고 부르겠습니다.

또한 분할하고 나온 배열에서의 첫 행 첫 열의 수를 시작하는 수라고 칭하겠습니다.

 

쪼개어진 배열에서 시작하는 수는

쪼개어지기 전 배열의 시작하는 수 + 배열의 사이즈 / 4 * (사분면-1)이 됩니다.

1 사분면은 쪼개어지기 전 배열의 시작하는 수 + 배열의 사이즈 / 4 * 0

2 사분면은 쪼개어지기 전 배열의 시작하는 수 + 배열의 사이즈 / 4 * 1

3 사분면은 쪼개어지기 전 배열의 시작하는 수 + 배열의 사이즈 / 4 * 2

4 사분면은 쪼개어지기 전 배열의 시작하는 수 + 배열의 사이즈 / 4 * 3

 

쪼개어진 배열의 시작하는 수를 찾았으니

언제까지 쪼개야 하는지와 어떤 배열을 쪼갤지를 알아낼 수 있으면 더욱 빠르게 

연산을 할 수 있습니다.

저는 분할 정복 함수를 호출할 때 총 6가지 인자를 넣어 줬습니다.

if (target_r >= left_r && target_r < right_r && target_c >= left_c && target_c < right_c) {
	divideAndConquer(n / 2, left_r, left_c, right_r - n / 2, right_c - n / 2, start + 0*(n * n/4));
	divideAndConquer(n / 2, left_r, left_c + n / 2, right_r - n / 2, right_c, start + 1*(n * n/4));
	divideAndConquer(n / 2, left_r + n / 2, left_c, right_r, right_c - n / 2, start + 2*(n * n/4));
	divideAndConquer(n / 2, left_r + n / 2, left_c + n / 2, right_r, right_c, start + 3*(n * n/ 4));
}

6가지 인자를 주지 않고 시작하는 점과 배열의 사이즈를 알면 끝나는 행과 열을 계산할 수 있지만

저는 그냥 시작하는 점과 끝나는 점 모두를 활용하였습니다.

 

분할을 반복하여 배열 사이즈가 n이 1 즉 배열의 사이즈가 1이 되면

이때 문제에서 요구하는 target_r과 left_r, target_c와 left_c가 같은지 확인하고

이때 이 배열의 수를 출력하면 문제가 풀립니다.

package b1074_Z;

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

public class Main {

	static int n, target_r, target_c;
	static int target;

	static void divideAndConquer(int n, int left_r, int left_c, int right_r, int right_c, int start) {

		if (n == 1) {
			if (left_r == target_r && left_c == target_c) {
				target = start;
			}
			return;
		}
		if (target_r >= left_r && target_r <= right_r && target_c >= left_c && target_c <= right_c) {
			divideAndConquer(n / 2, left_r, left_c, right_r - n / 2, right_c - n / 2, start + 0*(n * n/4));
			divideAndConquer(n / 2, left_r, left_c + n / 2, right_r - n / 2, right_c, start + 1*(n * n/4));
			divideAndConquer(n / 2, left_r + n / 2, left_c, right_r, right_c - n / 2, start + 2*(n * n/4));
			divideAndConquer(n / 2, left_r + n / 2, left_c + n / 2, right_r, right_c, start + 3*(n * n/4));
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inp = br.readLine().split(" ");
		n = Integer.parseInt(inp[0]);
		target_r = Integer.parseInt(inp[1]); //문제에서 원하는 r
		target_c = Integer.parseInt(inp[2]); //문제에서 원하는 c

		divideAndConquer((int) Math.pow(2, n), 0, 0, (int) Math.pow(2, n), (int) Math.pow(2, n), 0);
		System.out.println(target); //문제에서 원하는 r행c열의 탐색 순서 출력
	}
}