[백준] Z 1074 - 분할정복 JAVA

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

1074번: Z

코드설명

분할정복 문제입니다.

 

처음에 단순히 분할정복을 사용햇다가 시간초과가 걸렸습니다.

문제 조건에 시간제한으로 0.5초가 설정되어있어, map의 모든 구간을 검사한다면 시간초과가 납니다.

즉, 1, 2, 3, 4 사분면 중에 어디 범위에 속해있는지 체크하여 해당 사분면 범위에 속해있다면 그 부분만 재귀를 돌리면 됩니다.

 

범위처리 코드는 아래와 같습니다.

각 중간점을 기준으로 해당 중간점보다 작다면 좌측, 크다면 우측으로 처리합니다. (상하도 동일합니다.)

if( R < startR + nSize && C < startC + nSize) { //1사분면에 R,C 가 존재한다면.
    divideConquer(startR, startC, nSize);	
}
if( R < startR + nSize && C >= startC + nSize ) { // 2사분면에 R,C 가 존재한다면
    answer += (size * size) / 4;
    divideConquer(startR, startC + nSize, nSize);		
}
if( R >= startR + nSize && C < startC + nSize) {
    answer += ((size*size) / 4 ) * 2;
    divideConquer(startR + nSize, startC, nSize);
}
if( R >= startR + nSize && C >= startC + nSize) {
    answer += ((size * size) / 4 ) * 3;
    divideConquer(startR + nSize, startC + nSize, nSize);	
}

 

코드

범위처리를 통해 불필요한 재귀 생략.

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

public class Main {
	public static int N, R, C;
	public static char[][] map;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	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());
    	divideConquer(0, 0, (int) Math.pow(2, N));
    	
    }
	
	public static void divideConquer(int startR, int startC, int size) {
		
		if(size == 1) {
			System.out.println(answer);
			return ;
		}
		int nSize = size / 2;
		if( R < startR + nSize && C < startC + nSize) { //1사분면에 R,C 가 존재한다면.
			divideConquer(startR, startC, nSize);	
		}
		if( R < startR + nSize && C >= startC + nSize ) { // 2사분면에 R,C 가 존재한다면
			answer += (size * size) / 4;
			divideConquer(startR, startC + nSize, nSize);		
		}
		if( R >= startR + nSize && C < startC + nSize) {
			answer += ((size*size) / 4 ) * 2;
			divideConquer(startR + nSize, startC, nSize);
		}
		if( R >= startR + nSize && C >= startC + nSize) {
			answer += ((size * size) / 4 ) * 3;
			divideConquer(startR + nSize, startC + nSize, nSize);	
		}
		
	}
}

 

시간초과 나는 코드, 일반 분할정복사용

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

public class Main {
	public static int N, r, c;
	public static char[][] map;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	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());
    	divideConquer(0, 0, (int) Math.pow(2, N));
    }
	
	public static void divideConquer(int tempR, int tempC, int size) {
		
		if(size == 1 && tempR == r && tempC== c) {
			System.out.println(answer);
			System.exit(0);
			return ;
		}
		if(size == 1 ) { // size가 1일떄 한개를 검사하는것이므로 반드시 더하고 종료.
			answer += 1;
			return ;
		}
        // answer += 1; 여기에 처리하면 다 더해지지 않음.
		int nSize = size / 2;
		divideConquer(tempR, tempC, nSize);
		divideConquer(tempR, tempC + nSize, nSize); //여기서 재귀 호출시 Z 방향으로 작동되게 재귀호출합니다.
		divideConquer(tempR + nSize, tempC, nSize);
		divideConquer(tempR + nSize, tempC + nSize, nSize);
	}
}