문제
한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
인 경우, 배열을 크기가 인 네 구역으로 나눈 뒤 재귀적으로 순서대로 방문한다.
다음 예는 2^2 × 2^2 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
풀이
2^N x 2^N 배열을 전부 따라가면 비효율적이므로, 현재 찾고 싶은 칸이 어느 사분면에 있는지만 계속 좁혀 가면 된다. Z 순회는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 진행되므로, 앞선 사분면의 칸 수만큼 답에 미리 더할 수 있다.
현재 한 변 길이가 N인 정사각형을 절반으로 나누면 각 사분면의 크기는 half * half이다. 목표 칸 (r, c)가 어느 사분면에 속하는지에 따라 0, 1, 2, 3배의 half * half를 ans에 더하고, 좌표를 그 사분면 기준의 로컬 좌표로 바꿔 재귀를 이어 간다.
길이가 1이 되면 더 이상 나눌 수 없으므로 재귀를 끝내면 된다. 즉 이 문제는 실제 탐색이 아니라, 목표 칸 앞에 놓인 사분면들을 통째로 건너뛰며 방문 순서를 계산하는 분할 정복 문제다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int ans;
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());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
N = (int)Math.pow(2, N);
solve(r, c, N);
System.out.println(ans);
}
static void solve(int r, int c, int N) {
if (N == 1)
return;
int half = N / 2;
if (r < half && c < half) {
solve(r, c, half);
} else if (r < half) {
ans += half * half;
solve(r, c - half, half);
} else if (c < half) {
ans += half * half * 2;
solve(r - half, c, half);
} else {
ans += half * half * 3;
solve(r - half, c - half, half);
}
}
}복잡도
- 시간 복잡도:
- 공간 복잡도: 재귀 호출 스택 기준
마무리
배열을 직접 그릴 필요는 없고, 목표 칸이 속하지 않는 사분면을 한 번에 넘겨 버리면 된다. Z 문제의 핵심은 방문이 아니라 건너뛰기다.
