BOJ 1074 Z

https://www.acmicpc.net/problem/1074

1074번: Z

 

 

첫 번째 접근 방법은 분할과 정복/완탐 이었다.

 

재귀 함수에서

1. 1 2 3 4분면으로 나누고, 
2. Z방향대로 (1->2->3->4) 탐색해 순서를 세고,
3. 순서를 세는 중 찾는 위치를 만나면 탐색 순서를 출력

하는 방법으로 풀이했었으나, N이 최대 15이므로, 총 2^30 격자를 탐색하게 되는데, 주어진 시간 내에는 불가능한 방법이다.

 

두 번째 방법은

사분면으로 나눠 생각할 때, 찾는 위치(r, c)가 있는 사분면은 단 하나이다. 따라서 (r, c)가 위치한 사분면 이외의 사분면은 순서를 계산할 필요가 없다. 

사분면을 나누면 다음과 같다.

굳이 (1,3)이 존재하지 않는 1, 2 사분면을 탐색하지 않아도 8만큼의 순서가 이미 지난 것을 알 수 있다.

그다음

위에서처럼 3 사분면을 다시 사분면으로 나누고 (2, 0)~(3,1) 격자 내에 (1,3)이 포함되고, (1,3)이 포함되지 않는 1,2,3 사분면은 굳이 탐색하지 않아도 3만큼의 순서가 지난 것을 알 수 있다.

 

두 번째 방법은 위와 같이 4분면으로 나누고, 목표 지점이 위치한 사분면만 탐색하는 방법으로, 모든 칸의 z 움직임 탐색 없이 문제를 해결하는 방법이다.

 

#include <iostream>
using namespace std;
int N, r, c, cnt, mul;
void calc(int s_x, int s_y, int t_x, int t_y, int n) {
    int m_y = (s_y+t_y)/2, m_x = (s_x+t_x)/2;
    if(c<m_x) {
        if(r<m_y) // 1사분면
            mul = 0, t_x = m_x, t_y = m_y;
        else // 3사분면
            mul = 2, s_y = m_y+1, t_x = m_x;
    }
    else {
        if(r<m_y) // 2사분면
            mul = 1, s_x = m_x+1, t_y = m_y;
        else // 4사분면
            mul = 3, s_x = m_x+1, s_y = m_y+1;
    }
    n--;
    cnt+= mul*(1<<n)*(1<<n); // (r,c)가 존재하지 않는(탐색하지 않는) 격자들의 '넓이'/순서
    // mul 변수는 탐색하지 않고 지나치는 사분면의 수
    if(n<=0) { // 1x1 격자이면
        cout << cnt;
        return;
    }
    calc(s_x, s_y, t_x, t_y, n); // 시작 (r,c), 끝 (r,c)
}
int main() {
    cin >> N >> r >> c;
    int S = (1<<N);
    calc(0,0,S,S,N);
}

 코드는 위와 같고, 재귀함수 내에서 탐색할 구간의 시작과 끝 좌표를 정하고, 이외 사분면의 넓이/순서를 cnt변수에 더해주는 사실 이해하고 보면 간단한 코드이다.

---

재귀 함수는 특히 base case가 중요한데, n 변수 대신 좌표를 이용해 base case를 맞추려고 하니 작성하면서도 헷갈리고, 디버깅 과정에서도 이 값이 맞는 것인지 두 번 세 번 고민하게 만드는 마이너스 요소였다.

 

위와 같이 좌표를 수반하는 문제들은 작성할 때 가능하면 좌표보다는 위에서 size로 칭한 변수처럼 일정하게 변하는 변수를 추가해 실수와 피할 수 있는 고민을 줄이는 것도 좋은 방법일 것 같다.