[백준 1074] Z

Z

문제설명

위의 그림처럼 2차원 배열을 z모양으로 탐색한다. R과 C가 주어질 때 몇 번째로 방문하는지 출력하도록 하자.
이때 2차원배열의 크기는 N으로 첫 줄에 주어진다. 2의 n승이 되도록 한다.

---

알고리즘

1. N, R, C를 divide 함수에 크기와 x,y좌표를 전달해서 4개로 나누어 탐색을 시작한다.
2. divide함수는 조건이 있는데 해당하는 칸(x,y)좌표가 찾고자 하는 칸에 온다면 cnt값을 출력하고 종료한다. -> 현재 찾고자 하는 값에 도달했다는 의미이다.
3. 만약에 크기가 1인 경우 각각 계산하도록 한다.
4. 만약 찾으러 들어온 x,y의 좌표가 아예 구역에 해당하지 않고 다른 칸인 경우에는 제곱해서 계산을 더하고 종료시킨다. -> 시간 단축을 위함이다.
5. 위의 경우에도 해당하지 않는 경우 분할을 더 진행한다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int n, r, c;
int cnt;
bool check = false;
void divide(int num, int x, int y)
{
    if (x == r && y == c)//찾는 칸에 온 경우
    {
        cout << cnt << "\n";
        exit(0);
    }
    if (num == 1)//1칸 짜리인 경우 카운트
    {
        cnt++;
        return;
    }
    if (!((r >= x && r < x + num) && (c >= y && c < y + num)))//자른 부분에서 내가 찾는 칸이 전혀 없는 경우 계산후 반환
    {
        cnt += num * num;
        return;
    }

    divide(num / 2, x, y); //4구역중 왼쪽 위 부분 확인
    divide(num / 2, x, y + num / 2); //4구역 중 오른쪽 위 부분 확인
    divide(num / 2, x + num / 2, y); //4구역 중 왼쪽 아래 부분 확인 
    divide(num / 2, x + num / 2, y + num / 2); //4구역 중 오른쪽 아래 부분 확인
}

int main()
{        
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> r >> c;    
    divide(pow(2,n),0,0);//크기와 시작 좌표
    return 0;
}

---

고찰

이번 문제는 색종이 자르기와 매우 비슷한 문제였고, 그대로도 풀 수 있다. 하지만 2^15의 크기까지 고려해야하기 때문에 주어진 시간내에 결과를 낼 수 없다.
따라서 구역에 포함하지 않는 좌표를 연산하는 경우는 그냥 크기를 구해서 더하고 넘어가는 방식을 통해서 값을 빠르게 낼 수 있다.