[BaekJoon] 1074 Z

1.  문제 링크

2.  문제

요약

• 크기가 2^N * 2^N인 2차원 배열을 2 * 2인 배열의 경우 Z모양으로 방문하고 N > 1인 경우 2^(N - 1) * 2^(N - 1)로 4등분하여 재귀적으로 순서대로 방문하려고 합니다.
• N이 주여졌을 때, r행 c열을 몇 번째로 방문하는지를 찾아내는 문제입니다.
• 방문순서는 위 그림을 참조할 수 있습니다.
• 입력: 첫 번째 줄에 N, r, c가 주어집니다.
• 출력: N에 대하여 r행 c열을 몇 번째로 방문하는지를 출력합니다.

3.  소스코드

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 count = 0;
	public void findNum(int size, int row, int col) {
		if(size == 1)
			return;
		if(row < size / 2 && col < size / 2) {
			findNum(size / 2, row, col);
		} else if(row >= size / 2 && col < size / 2) {
			count += (size * size / 4) * 2;
			findNum(size / 2, row - size / 2, col);
		} else if(row < size / 2 && col >= size / 2) {
			count += size * size / 4;
			findNum(size / 2, row, col - size / 2);
		} else {
			count += (size * size / 4) * 3;
			findNum(size / 2, row - size / 2, col - size / 2);
		}
	}
	
	public void getVisitNth(int size, int row, int col) {
		int n = (int)Math.pow(2, size);
		findNum(n, row, col);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		br.close();
		StringTokenizer st = new StringTokenizer(input);
		int size = Integer.parseInt(st.nextToken());
		int row = Integer.parseInt(st.nextToken());
		int col = Integer.parseInt(st.nextToken());
		Main m = new Main();
		m.getVisitNth(size, row, col);
		bw.write(count + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 주어진 배열을 4등분하여 같은 동작을 반복하기 때문에 재귀를 이용하여 해결할 수 있습니다.
• 4등분을 한 것을 기준으로 왼쪽 위를 1사분면, 오른쪽 위를 2사분면, 왼쪽 아래를 3사분면, 오른쪽 아래를 4사분면으로 봤을 때 각 사분면은 아래와 같은 규칙으로 방문됩니다.
• 1사분면에 속한다면, 이전에 아무 곳도 방문하지 않았으므로 방문된 순서는 그대로 둡니다.
• 2사분면에 속한다면, 이전에 1사분면을 방문했기 때문에 (2^N * 2^N) / 4가 방문된 순서에 반영됩니다.
• 3사분면에 속한다면, 이전에 1,2사분면을 방문했기 때문에 (2^N * 2^N) / 4 * 2가 방문된 순서에 반영됩니다.
• 4사분면에 속한다면, 이전에 1,2,3사분면을 방문했기 때문에 (2^N * 2^N) / 4 * 3이 방문된 순서에 반영됩니다.
• 위 규칙을 바탕으로 재귀를 진행하면 방문된 순서를 찾을 수 있습니다.

1. 주어진 N에 대해 2차원 배열의 길이는 2^N이므로 이를 n이라는 변수에 저장합니다.
2. n, r, c를 바탕으로 재귀를 진행합니다.
• 만약 n이 1이 됐다면 재귀를 마칩니다.
• r과 c가 n의 반보다 작다면 이는 1사분면에 해당하는 것이므로 n만 반으로 줄여서 재귀를 진행합니다.
• r이 n의 반보다 작고 c가 n의 반보다 크거나 같다면 이는 2사분면에 해당하는 것이므로 방문된 순서를 나타내는 변수인 count에 n * n / 4를 더해주고 n을 반으로 줄이고 c는 그 다음 연산에서 상대위치로서 n의 반을 해준 것 내부에서 어느 곳에 위치해있는지를 알려줘야 하므로 n의 반을 빼준 후에 재귀를 진행합니다.
• r이 n의 반보다 크거나 같고 c가 n의 반보다 작다면 이는 3사분면에 해당하는 것이므로 방문된 순서를 나타내는 변수인 count에 n * n / 4 * 2를 더해주고 n을 반으로 줄이고 r은 그 다음 연산에서 상대위치로서 n의 반을 해준 것 내부에서 어느 곳에 위치해있는지를 알려줘야 하므로 n의 반을 빼준 후에 재귀를 진행합니다.
• r이 n의 반보다 크거나 같고 c가 n의 반보다 크거나 같다면 이는 4사분면에 해당하는 것이므로 방문된 순서를 나타내는 변수인 count에 n * n / 4 * 3을 더해주고 n을 반으로 줄이고 r과 c는 그 다음 연산에서 상대위치로서 n의 반을 해준 것 내부에서 어느 곳에 위치해있는지를 알려줘야 하므로 각각 n의 반을 빼준 후에 재귀를 진행합니다.
3. n이 1이 되어 재귀를 마치면 그 때의 count 값이 r행 c열의 방문 순서가 됩니다.