[C++] 백준 1074: Z

문제 이해

- 크기가 2^N * 2^N인 2차원 배열

- Z모양으로 탐색하고자 한다.

- N > 1인 경우, 배열을 크기가 2^(N-1) * 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다.

- N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하라.

 

<조건>

- 시간 제한: 0.5초

- 메모리 제한: 512MB

 

<입력>

- N: 배열의 크기 관련 정수 (1 ~ 15)

- r, c: 몇 번째로 방문하는지 찾아야하는 좌표 (0 ~ 2^N-1)

 

<출력>

- (r, c)를 몇 번째로 방문했는지 출력하라.

 

 

---

문제 풀이

4등분을 한다는 것에 분할정복 문제라는 것을 체크했다.

 

 

 

처음에는 단순히 4사분면으로 나누어 분할정복하여 각 방문마다 +1씩 해주었다.

하지만, 이 풀이는 시간 초과였다.

 

 

 

결국 인터넷 풀이를 참고하여 문제를 풀었다.

 

 

이 문제의 핵심은 (r, c)가 사분면 안에 위치하는지 체크하는 것이다!

if(r >= y && r < y + size && c >= x && c < x + size){
    solve(y, x, n-1);
    solve(y, x+size/2, n-1);
    solve(y+size/2, x, n-1);
    solve(y+size/2, x+size/2, n-1);
}

 

 

 

Z방향으로 탐색했을 때, 안에 존재하지 않는다면 사분면의 넓이만큼 더해주면 된다.

else{
    cnt += size * size;
}

 

 

 

---

주의할 점

1. 처음 좌표를 방문한 경우에는 0 번째로 체크해야 한다.

-> 예제를 통해 확인할 수 있다.

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 987654321

int n, r, c;
int cnt = 0;
int ans;

void solve(int y, int x, int n){
    if(y == r && x == c){
        cout<<cnt;
        return; 
    }

    int size = (int)pow(2, n);
    if(r >= y && r < y + size && c >= x && c < x + size){
        solve(y, x, n-1);
        solve(y, x+size/2, n-1);
        solve(y+size/2, x, n-1);
        solve(y+size/2, x+size/2, n-1);
    }else{
        cnt += size * size;
    }

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>r>>c;

    solve(0, 0, n);

    return 0;
}