BOJ01074 Z

https://www.acmicpc.net/problem/1074 (opens new window)

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

분할 정복

분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.

위 문제의 경우 유효한 좌표를 분할하여 재귀적으로 정복한다. 순서는 Z자로 2사분면 -> 1사분면 -> 3사분면 -> 4사분면으로 진행된다. 여기서 말하는 유효한 좌표란, 입력으로 주어진 좌표를 포함하는 범위이다.

private static boolean isValidScope(int row, int col, int size) {
    if (row > r || row + size <= r || col > c || col + size <= c) {
        return false;
    }

    return true;
}

이렇게 설정한 이유는 문제에서 N은 최대 15까지 될 수 있다. 2^15 * 2^15은 대략 10억 정도의 엄청나게 큰 수이기 때문에 모든 배열을 생성하여 count 값을 저장 하는 것은 메모리를 과도하게 사용하는 결과를 낳았다.

그렇기 때문에 유효한 좌표인 경우에만 정복을 진행하고, 아닌 경우에는 현재 탐색하는 size * size만큼 count해준다.

private static void partition(int row, int col, int size) {

    if (row == r && col == c) {
        System.out.println(count);
        return;
    }

    if (isValidScope(row, col, size)) {
        int halfSize = size / 2;
        partition(row, col, halfSize); // 2사분면
        partition(row, col + halfSize, halfSize); // 1사분면
        partition(row + halfSize, col, halfSize); // 3사분면
        partition(row + halfSize, col + halfSize, halfSize); // 4사분면
    } else {
        count += size * size;
    }
}

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ1074 {

    private static int n, r, c, count;

    private static void partition(int row, int col, int size) {

        if (row == r && col == c) {
            System.out.println(count);
            return;
        }

        // 유효한 범위인 경우
        if (isValidScope(row, col, size)) {
            int halfSize = size / 2;
            partition(row, col, halfSize); // 2사분면
            partition(row, col + halfSize, halfSize); // 1사분면
            partition(row + halfSize, col, halfSize); // 3사분면
            partition(row + halfSize, col + halfSize, halfSize); // 4사분면
        } else {
            count += size * size;
        }
    }

    private static boolean isValidScope(int row, int col, int size) {
        if (row > r || row + size <= r || col > c || col + size <= c) {
            return false;
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        r = scanner.nextInt();
        c = scanner.nextInt();
        int size = (int) Math.pow(2, n);

        partition(0, 0, size);
    }
}

#algorithm #BOJ #분할 정복 #재귀