Baekjoon_1074_Z

문제 설명

• 2의 N제곱 * 2의 N제곱인 2차원 배열을 계속 4등분
• r행 c열을 몇 번째로 방문하는지 출력

 

문제 풀이

재귀를 통해서 점점 아래 단계로 내려가고, (r,c)를 만났을 때 그 때까지 만난 칸의 개수를 출력하는 문제이다.

 

2차원 배열의 크기 (2의 N제곱 * 2의 N제곱)를 4등분 한 후, 좌상, 우상, 좌하, 우하 순서로 (r,c)가 각 부분에 포함되는지 확인했다.

 

각 부분에 포함되지 않으면 그 부분에 있는 칸의 개수(num/2 * num/2)를 더해주었다.

 

해당 부분에 (r,c)가 포함되면 재귀를 통해 그 부분을 다시 4등분하는 과정을 반복한다.

 

최종적으로 (r,c)에 도달하면 true를 반환하여 재귀를 종료하고 답을 출력하였다.

 

처음에는 모든 파트를 돌면서 재귀를 통해 답을 구했는데, 시간초과되었다.

 

하여 위와 같은 방식으로 문제를 해결했다.

 

문제 풀이 코드

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

public class _1074_Z {
	static int N,r,c,answer = 0;
	static int dr[] = {0,0,1,1};	//좌상,우상,좌하,우하
	static int dc[] = {0,1,0,1};
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		dynamic((int)Math.pow(2, N),0,0);	//2차원 배열의 크기,0,0으로 시작
		System.out.println(answer);
	}
	static boolean dynamic(int num, int rr, int cc) {
		if(rr == r && cc == c) {	// r,c를 만났을 때 true반환
			return true;
		}
		for(int i = 0; i<4;++i) {
			if(rr+dr[i]*num/2 <= r && rr+dr[i]*num/2+num/2 > r &&
					cc+dc[i]*num/2 <= c && cc+dc[i]*num/2+num/2 > c) {	//4등분한 2차원배열 파트 각각에 (r,c)가 포함되는지 확인
				if(dynamic(num/2,rr+dr[i]*num/2,cc+dc[i]*num/2))	// (r,c)가 포함되는 배열 파트에 재귀를 통해 접근
					return true;									// r,c를 만났을 때 true반환
			}
			else {
				answer += (num/2 * num/2);	//(r,c)가 포함되는 배열 파트가 아니라면 해당 파트에 있는 칸의 개수 모두 더해주기
			}
		}
		return false;
	}
}