[백준] 1074 Z

 

 

문제에 대한 설명은 아래 링크를 들어가서 확인하도록 하자.

www.acmicpc.net/problem/1074

1074번: Z

 

이 문제는 단순한 탐색 문제로 볼 수도 있다. Z 방향대로 탐색하여 탐색할 좌표의 번호를 출력하면 된다. 하지만 0부터 N까지 모조리 탐색해 버리면 시간초과가 뜬다.

 

그렇다면 어떻게 접근하는 것이 좋을까? 답은 확실하게 공간을 차지하는 곳에 대해서는 탐색을 진행하지 않는 것이다. 다음 사진을 예시로 들어 보자.

 

 

입력이 3 3 7 일 경우를 생각해보자. 어쨋거나 답은 63이 나올 것이다. 63을 도출하기 위해서 0부터 63까지 모두 탐색하는 방법도 생각해 볼 수 있다.

 

그러나 여기서 획기적으로 시간을 줄일 수 있는 방법이 있다. 바로 탐색을 시작할 때 4개의 구역으로 나눈 뒤, 0부터 15까지는 확실하게 영역에 포함되지 않으므로 통과가 가능하다. 이와 같은 방법으로 나머지 3개의 영역에 대해서도 통과를 할 수가 있다. 그렇게 되면 64번 탐색할 것을 4번의 탐색으로 간소화 시킬 수 있다.

 

이러한 생각을 바탕으로 코드를 작성해 보자.

 

#include <iostream>
#include <math.h>
using namespace std;
 
int r, c, ans;
 
void find(int x, int y, int size)
{
    /*좌표를 찾았을 경우*/
    if (x == r && y == c)
    {
        cout << ans << endl;
        return;
    }
    /*해당 영역 내에 있을 경우*/
    if (r < x + size && r >= x && c < y + size && c >= y)
    {
        find(x, y, size / 2);
        find(x, y + size / 2, size / 2);
        find(x + size / 2, y, size / 2);
        find(x + size / 2, y + size / 2, size / 2); 
    }
    /*좌표를 찾지 못하였을 경우*/
    else
        ans += pow(size,2); 
}
 
int main()
{
    int N;
 
    cin >> N >> r >> c;
    ans = 0;
    find(0, 0, pow(2, N));
}

 

24번째 줄에 생략할 수 있는 계산이 존재하면 바로 생갹시키는 것을 볼 수 있다.