백준 1074 - Z(자바 - 분할정복)

쿼드 트리를 익힌지 얼마 안되서 마주한 응용 문제

이 문제는 일반적인 쿼드 트리 구현으로 풀이를 해보다가 메모리 초과, 시간 초과를 몇번이나 맞닥 뜨린 끝에 질문 검색글을 보다가 얻은 힌트를 통해 겨우 풀이에 성공한 문제이다.

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

1074번: Z

 

일단 이 문제의 경우 기본적으로 쿼드 트리의 개념을 사용해야 하는것은 맞다.

그러나 조금 다른것이, 지금까지 했던 것처럼 쿼드 트리 자료구조를 통해 각 사분면 별로 요구하는 조건에 맞을 때까지 모두 다 4분할을 진행한다면 반드시 시간 제한에 걸려서 문제 풀이 통과를 하지 못하게 된다.

 

그렇기 때문에 이 문제를 해결하려면 사분면을 분할하면서 찾고자 하는 좌표에 대한 탐색 횟수를 계산하되, 재귀 함수 수행때마다 만들어지는 사분면을 전부 다 4분할 하는 것이 아니라, 찾기를 원하는 좌표가 포함된 사분면 하나만을 선택해서 따로 떼어 내듯이 프로세스를 진행시켜야 시간 제한을 초과하지 않고 문제 풀이를 통과 할 수 있다.

 

즉, 지금까지와는 다르게 사분면을 4분할하기 위해 메소드의 각 수행때마다 재귀 함수를 4번 호출하는 것이 아니라, 좌표의 범위가 2 X 2 의 크기가 되지 않는한, 즉 현재 사분면의 추가적인 분할이 가능한 동안 각 범위에 맞는 사분면의 좌표 범위를 입력값으로 가지는 재귀 함수 하나만을 호출해줘야 한다.

 

여기서 주의해야할 점은 다음과 같다.

1. 왼쪽 위 사분면을 호출할 경우 탐색 횟수를 증가시키지 않는다.

2. 오른쪽 위 사분면을 호출할 경우 왼쪽 위 사분면을 탐색한 횟수만큼 탐색횟수를 증가시킨다. 

3. 왼쪽 아래 사분면을 호출할 경우 왼쪽 위, 오른쪽 위 사분면을 탐색한 횟수만큼 탐색횟수를 증가시킨다.

4. 오른쪽 아래 사분면을 호출할 경우 왼쪽 위, 오른쪽 위, 왼쪽 아래 사분면을 탐색한 횟수만큼 탐색 횟수를 증가시킨다.

 

그리고 마지막으로 더 이상 분할할 수 없을 정도로 분할한 이후(2 X 2) 현재 좌표 범위를 기준으로 찾고자 하는 인덱스를 탐색하여(계속 찾고자 하는 인덱스를 향해 좌표 범위를 2 X 2 크기 까지 좁혀왔다.)

현재 좌표 범위에서 몇번째 탐색을 하면 찾고자 하는 좌표에 도착하는지 계산 한 다음, 그 값을 전체 탐색횟수에 추가해주는 것으로 문제 풀이를 끝낸다.

 

코드는 다음과 같다.

- Main.java

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

public class Main {
	
	static int searchCount = 0;
	static int r = 0;
	static int c = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		int arraySize = (int) Math.pow(2, n);
		
		divideAndconquer(0, arraySize, 0, arraySize);
	}

	private static void divideAndconquer(int x1, int x2, int y1, int y2) throws IOException {
		
		
		if(x2 - x1 != 2 && y2 - y1 != 2) {
			// 위치에 따라 한 가지 사분면만을 선택해 재귀 호출 수행
			// 몇 사분면으로 가는지에 따라 탐색 횟수를 늘려준다.
			
			// 왼쪽 위 사분면(탐색 횟수 중가 x)
			if(r >= x1 && r < (x1+x2)/2 && c >= y1 && c < (y1+y2)/2) {
				divideAndconquer(x1, (x1+x2)/2, y1, (y1+y2)/2);
			}	
			// 오른쪽 위 사분면 (왼쪽 위 사분면을 탐색한 횟수만큼 증가)
			else if(r >= x1 && r < (x1+x2)/2 && c >= (y1+y2)/2 && c < y2) {
				searchCount += ((x1+x2)/2 - x1) * ((y1+y2)/2 - y1);
				divideAndconquer(x1, (x1+x2)/2, (y1+y2)/2, y2);
			}	
			// 왼쪽 아래 사분면 (왼쪽 위, 오른쪽 위 사분면을 탐색한 횟수 만큼 증가)
			else if(r >= (x1+x2)/2 && r < x2 && c >= y1 && c < (y1+y2)/2) {
				searchCount += 2 * (((x1+x2)/2 - x1) * ((y1+y2)/2 - y1));
				divideAndconquer((x1+x2)/2, x2, y1, (y1+y2)/2);
			}	
			// 오른쪽 아래 사분면 (왼쪽 위, 오른쪽 위, 왼쪽 아래 사분면을 탐색한 횟수 만큼 증가)
			else {
				searchCount += 3 * (((x1+x2)/2 - x1) * ((y1+y2)/2 - y1));
				divideAndconquer((x1+x2)/2, x2, (y1+y2)/2, y2);
			}	
		}
		
		else {
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			
			if(x1 == r && y1 < c)
				searchCount++;
			else if(x1 < r && y1 == c)
				searchCount += 2;
			else if(x1 < r && y1 < c)
				searchCount += 3;
			
			bw.write(searchCount + "\n");
			bw.flush();
			bw.close();
		}
	}
}