[백준] 1074 Z

문제

---

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

 

 

풀이

---

이 문제는 분할정복을 이용하는 문제다.

 

재귀를 이용해서 하나씩 방문하며 모든 값을 찾아내면 시간초과가 뜬다.

 

재귀의 방식을 이용하돼 해당 인덱스가 위치에 없다면 현재까지의 분할된 배열의 갯수를 더해주면 된다.

 

위 그림에서 배열을 예시로 13번째 배열의 위치에 값을 알아내기 위해서는 네개로 쪼개어 확인을 해야한다.

13번째 배열의 r = 2, c = 3 이다.

 

전체를 4등분 하면 아래와 같이 된다. 여기서 적힌 차례대로 방문을 해야한다. 여기서 구하고자 하는 r 과 c 의 값이 해당 범위 안에 없다면, 배열의 갯수를 더해주면 된다.

1.

r : 0 ~ 1  

c : 0 ~ 1  

r 과 c 모두 범위 밖이기 때문에 2 * 2 = 4를 더해준다.

2.

r : 0 ~ 1  

c : 2 ~ 3

r의 범위 밖이기 때문에 4를 더해준다.

3.

r : 2 ~ 3

c : 0 ~ 1

c의 범위 밖이기 때문에 4를 더해준다.

4.

r : 2 ~ 3

c : 2 ~ 3

범위 안이기 때문에 다시 4등분하여 재귀를한다. 하고나면 2번째로 방문하는 곳이기 때문에 값이 13이라는 것을 알 수 있다.

 

위와같은 방식으로 직접 모두 방문하지 않고 해당 배열의 갯수를 더하는 방식으로 원하는 위치의 값을 구했다.

핵심코드는 아래와 같다.

static void solution(int startR, int startC, int endR, int endC) {
	
	if(endR <= startR || endC <= startC) {return;}
	
	if(startR == r && startC == c) {
		sb.append(index);
		return;
	}
	
	if(startR <= r && endR > r && startC <= c && endC > c) {
	
		int divR = (endR - startR) / 2;
		int divC = (endC - startC) / 2;
		
		solution(startR, startC, startR + divR, startC + divC);
		solution(startR, startC + divC, startR + divR, endC);
		solution(startR + divR, startC, endR, startC + divC);
		solution(startR + divR, startC + divC, endR, endC);
	}
	else {
		index += (endR - startR) * (endC - startC);
	}
}

 

 

 

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int[][] board;
	static int index;
	static int n, r, c;
		
	static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		n = parseInt(st.nextToken());
		r = parseInt(st.nextToken());
		c = parseInt(st.nextToken());
		
		index = 0;
		solution(0, 0, (int)Math.pow(2, n), (int)Math.pow(2, n));
		
		System.out.println(sb);
	}
	
	static void solution(int startR, int startC, int endR, int endC) {
		
		if(endR <= startR || endC <= startC) {return;}
		
		if(startR == r && startC == c) {
			sb.append(index);
			return;
		}
		
		if(startR <= r && endR > r && startC <= c && endC > c) {
		
			int divR = (endR - startR) / 2;
			int divC = (endC - startC) / 2;
			
			solution(startR, startC, startR + divR, startC + divC);
			solution(startR, startC + divC, startR + divR, endC);
			solution(startR + divR, startC, endR, startC + divC);
			solution(startR + divR, startC + divC, endR, endC);
		}
		else {
			index += (endR - startR) * (endC - startC);
		}
	}
}