[C++] BOJ 1074 : Z

 

 

 

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

 

 

문제 3줄 요약

1. 2^N x 2^N 크기의 2차원 배열을 Z모양으로 탐색한다.

2. 순서는 왼쪽 위 / 오른쪽 위 / 왼쪽 아래 / 오른쪽 아래 순으로 Z 모양이다.

3. r행 c열은 몇 번째로 방문하는지 출력해라!

 

---

 

N=3일 경우는 아래와 같이 탐색한다.

 

 

그림만 봐도 끔찍하다.

 

이번 문제는 큰 문제를 작은 문제로 나누어서 해결하는

분할 정복 문제이다.

 

따라서 Z모양으로 탐색하는 부분과

재귀를 통한 2 x 2 사각형 탐색하는 부분이 필요하다.

 

작성된 코드를 보고 분석해보자.

 

---

 

    if(pow(2,w-1) != 1){
        for(int i=x; i<x+pow(2,w); i+=pow(2,w-1)){
            for(int j=y; j<y+pow(2,w); j+=pow(2,w-1)){
                if(i<=r && r<i+pow(2,w-1) && j<=c && c<j+pow(2,w-1)){
                    zFunc(i, j, w-1);
                }else if(!chk){
                    answer += (pow(2,w-1)*pow(2,w-1));
                }
            }
        }
    }

 

한 변의 길이가 2^w이며, (x, y) 좌표부터 시작하는 사각형은

2x2 길이의 사각형로 나눠질 때까지 zFunc 함수를 재귀적으로 반복한다.

 

이때 크게 나누어진 4개의 사각형을 모두 재귀적으로 반복하는 것이 아닌

4사분면 중 우리가 필요한 좌표인 (r, c)가 있는 사분면만 재귀로 탐색한다.

 

아래 그림을 살펴보자.

 

 

(3, 1)은 첫 zFunc 함수에서 1사분면에 해당된다.

따라서 2~4사분면은 탐색하지 않는다.

 

 

재귀로 들어간 두 번째 zFunc 함수에서는 3사분면에 해당된다.

4사분면은 탐색을 하지 않으며, 1~2사분면은 방문했다는 카운트를 해줘야한다.

 

 따라서 chk가 false인 경우에는

먼저 방문해야하는 사분면을 카운트 해주고

우리가 찾고자하는 좌표의 사분면으로 넘어간다.

 

그 이후의 사분면은 무시해주면 된다.

 

---

 

    else if(pow(2,w-1) == 1){
        int dx[4] = {0, 0, 1, 1};
        int dy[4] = {0, 1, 0, 1};

        for(int i=0; i<4; i++){
            if(x+dx[i]==r && y+dy[i]==c) {
                chk = true;
                break;
            }
            answer++;
        }
    }

 

만약 재귀 도중 우리가 찾고자하는 2x2 사각형의 사분면을 찾았다면,

왼쪽 위 / 오른쪽 위 / 왼쪽 아래 / 오른쪽 아래 순서대로 탐색하며

일치하는 좌표를 찾고 체크해준다.

 

이때 방문 카운트 또한 수행해준다.

 

---

 

위의 모든 과정을 합치면 아래와 같이 작성할 수 있겠다.

 

#include <iostream>
#include <cmath>

using namespace std;

int n, r, c, answer;
bool chk;

void zFunc(int x, int y, int w){
    if(chk) return;

    if(pow(2,w-1) != 1){
        for(int i=x; i<x+pow(2,w); i+=pow(2,w-1)){
            for(int j=y; j<y+pow(2,w); j+=pow(2,w-1)){
                if(i<=r && r<i+pow(2,w-1) && j<=c && c<j+pow(2,w-1)){
                    zFunc(i, j, w-1);
                }else if(!chk){
                    answer += (pow(2,w-1)*pow(2,w-1));
                }
            }
        }
    }
    else if(pow(2,w-1) == 1){
        int dx[4] = {0, 0, 1, 1};
        int dy[4] = {0, 1, 0, 1};

        for(int i=0; i<4; i++){
            if(x+dx[i]==r && y+dy[i]==c) {
                chk = true;
                break;
            }
            answer++;
        }
    }
}

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    cin >> n >> r >> c;

    zFunc(0, 0, n);

    cout << answer;
    return 0;
}

 

사분면 체크없이 모든 사분면을 순서대로 재귀를 통해 반복한다면

시간 초과가 발생한다.

 

끝!