분류
분할 정복, 재귀
문제 설명
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 22 × 22 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
예제 입력
2 3 13 7 71 0 04 7 710 511 51110 512 512
예제 출력
1163063262143786432
코드 - Z.java
import java.io.*;
import java.util.*;
public class Main {
static int N, r, c; // N은 2의 N승의 배열 크기, r과 c는 찾고자하는 좌표
static int count = 0; // (r, c)를 방문할 때까지의 카운트
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader
StringTokenizer st = new StringTokenizer(br.readLine()); // 입력값 분리를 위한 StringTokenizer
N = Integer.parseInt(st.nextToken()); // 배열의 크기 2^N x 2^N
r = Integer.parseInt(st.nextToken()); // 타겟의 행 좌표
c = Integer.parseInt(st.nextToken()); // 타겟의 열 좌표
z((int)Math.pow(2, N), 0, 0); // Z 모양으로 탐색 시작. 시작 크기는 2^N
}
public static void z(int size, int x, int y) {
// 현재 위치 (x, y)가 우리가 찾고자 하는 (r, c)인지 확인
if (x == r && y == c) {
System.out.println(count); // 찾았다면 현재까지의 카운트 출력
return;
}
// 현재의 size로 분할된 영역 내에 (r, c)가 존재하는 경우
if (r < x + size && r >= x && c < y + size && c >= y) {
int newSize = size / 2; // 현재 크기의 절반으로 축소
z(newSize, x, y); // 왼쪽 위 영역 탐색
z(newSize, x, y + newSize); // 오른쪽 위 영역 탐색
z(newSize, x + newSize, y); // 왼쪽 아래 영역 탐색
z(newSize, x + newSize, y + newSize); // 오른쪽 아래 영역 탐색
} else {
// (r, c)가 현재 영역에 존재하지 않으면 그 영역은 전부 건너뛰기 때문에
// 카운트에 현재 영역의 크기만큼 더해줌
count += size * size;
}
}
}
코드 분석하기
Z-Order 탐색 알고리즘 코드 분석
문제 설명:
$2^N$ x $2^N$ 크기의 행렬에서 Z-Order 탐색 방식을 사용하여 (r, c) 위치에 도달할 때까지의 방문 순서를 구하는 문제입니다.
코드 분석:
- 전역 변수 선언:
static int N, r, c;
static int count = 0;
- N: $2^N$ x $2^N$ 크기의 행렬을 나타냅니다.
- r, c: 우리가 찾고자하는 위치입니다.
- count: (r, c)에 도달할 때까지의 방문 순서를 저장합니다.
- main 함수: 입력을 받고 초기 z 함수를 호출합니다.
N = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
z((int)Math.pow(2, N), 0, 0);
- z 함수: Z-Order 탐색 알고리즘이 구현된 재귀 함수입니다.
- Base Condition: 현재 위치 (x, y)가 우리가 찾고자 하는 (r, c) 위치와 동일한지 확인합니다. 동일하면, 현재까지의 카운트 값을 출력하고 함수를 종료합니다.
if (x == r && y == c) {
System.out.println(count);
return;
}
- 재귀 호출: 주어진 크기의 영역 내에서 (r, c)가 존재하면 현재 영역을 4개의 작은 영역으로 나누고 해당 영역에 대해 재귀적으로 탐색을 계속합니다.
int newSize = size / 2;
z(newSize, x, y);
z(newSize, x, y + newSize);
z(newSize, x + newSize, y);
z(newSize, x + newSize, y + newSize);
- 영역을 건너뛰기: 만약 (r, c)가 현재 영역에 없다면, 해당 영역을 전체적으로 건너뛰게 됩니다. 이 때 count는 해당 영역의 크기만큼 증가시킵니다. 이는 건너뛴 모든 셀들을 방문했다고 가정하기 때문입니다.
count += size * size;
결론:
이 코드는 Z-Order 탐색 방법을 통해 특정 좌표에 도달할 때까지의 방문 순서를 구하는 문제에 대한 해결책을 제시합니다. 분할 정복 알고리즘의 핵심 원리를 활용하여 큰 문제를 작은 문제로 분할하고, 그 작은 문제를 재귀적으로 해결하는 방식을 보여줍니다. 이러한 접근 방식은 불만이나 비효율성 없이 큰 행렬에 대한 조회를 빠르게 수행할 수 있게 해줍니다.
백준에서 문제 풀어보기
https://www.acmicpc.net/problem/1074
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
