BOJ 1074 - Z 문제풀이

문제를 읽고 이해하기

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

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

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

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

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

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

재정의와 추상화

전형적인 분할 정복 문제이지만, 그 구현부가 조금 독특하다는 점이 특징이다.

• 주어진 길이가 2일 때까지 계속 4등분한다. 4등분할 때 순서는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서(Z)를 꼭 지켜주어야 한다.
• 주어진 길이가 2일 경우, 아까 언급한 순서를 지켜 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 방문한다. 방문할 때마다 cnt 값을 1씩 증가시키고, 만약 좌표가 (r, c)일 경우 진행을 중단한다.

코드 작성

#include <iostream>
#include <cmath>
using namespace std;

typedef struct {
    int y, x;
} Position;

Position pos[4] = {
        {0, 0},
        {0, 1},
        {1, 0},
        {1, 1}
};

int n, r, c, cnt;

bool divide_and_conquer(int y, int x, int length) {
    if (length != 2) {
        if (divide_and_conquer(y, x, length / 2)) return true;
        if (divide_and_conquer(y, x + length / 2, length / 2)) return true;
        if (divide_and_conquer(y + length / 2, x, length / 2)) return true;
        if (divide_and_conquer(y + length / 2, x + length / 2, length / 2)) return true;
        return false;
    }
    for (auto & p : pos) {
        int now_y = y + p.y;
        int now_x = x + p.x;
        cnt++;
        if (now_y == r && now_x == c) return true;
    }
    return false;
}

int main() {
    cin >> n >> r >> c;
    divide_and_conquer(0, 0, pow(2, n));
    cout << cnt - 1;
    return 0;
}