[ 백준 1074 ] Z (C++)

백준의 Z(1074) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

입력으로 주어지는 (행, 열)에 존재하는 숫자를 찾아야 하는 문제이다.

가장 먼저 우리가 알 수 있는 것은 'Z'모양 하나가 나오기 위해서는 현재 탐색하고자 하는 범위가 2 x 2 크기여야 한다는 것이다.

그래서 본인은 현재 탐색하려는 맵의 범위가 '2x2' 형태가 될 때 까지 재귀를 통해서 나눠주었다.

2 x 2 가 되었다면 'Z' 모양을 그리는 순서에 맞게 4칸을 모두 탐색하면서 우리가 찾고자 하는 (행, 열)이 존재하는지 찾으면 된다.

하지만 ! 우리가 구해야 하는 것은 해당 (행, 열)에 존재하는 숫자이다. 이 숫자를 구하기 위해서 하나의 전역변수를 선언해서 사용해 주었다. 초기값은 0인 변수이다. 2 x 2 가 되었을 때, 단순히 4칸을 탐색하는 것이 아니라 탐색하면서 선언해놓은 이 전역변수

값을 계속해서 ++ 시켜주었다. 그래서 만약 우리가 찾는 (행, 열)이 존재하는 2 x 2 영역이라면, 이 전역변수를 그대로 출력시켜

주면 되는 것이고, 그게 아니라면 그 다음 탐색을 진행하면 된다.

이렇게 되면, 그 다음 탐색을 진행할 때, 이전의 영역에서 ++ 시켜놓은 값이 있기 때문에 문제에서 주어진 맵과 같은 형태로

숫자를 구할 수 있다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int N, R, C;
int Answer;
 
int dx[] = { 0, 0, 1, 1 };
int dy[] = { 0, 1, 0, 1 };
 
void Input()
{
    cin >> N >> R >> C;
}
 
void DFS(int x, int y, int Size)
{
    if (Size == 2)
    {
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx == R && ny == C)
            {
                cout << Answer << endl;
                return;
            }
            Answer++;
        }
        return;
    }
 
    DFS(x, y,  Size / 2);
    DFS(x, y + Size / 2, Size / 2);
    DFS(x + Size / 2, y, Size / 2);
    DFS(x + Size / 2, y + Size / 2, Size / 2);
}
 
void Solution()
{
    DFS(0, 0, 1 << N);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}