[PS] 백준 #1074 Z 문제풀이

[ 문제 풀이 ]

• Problem : 백준 # 1074
• 구분 : 재귀, 분할정복
• 난이도 : Silver 1
• 풀이 방법 :
  • 기본적으로 2✗2인 배열에서 Z 모양으로 이동하고 있으므로, 방문순서를 좌표로 나타내면 (0,0) -> (0,1) -> (1,0) -> (1,1) 가 됩니다.
  • 2N✗2N인 배열은 배열을 4개로 쪼개서 차례대로 Z 이동을 반복한다고 하였으므로, 크기가 2✗2가 될때까지 재귀적으로 Z 이동 위치 순서대로 함수를 호출해줍니다.
  • 이때 2N✗2N 배열에서 방문순서 좌표는 2✗2 좌표에서 N배만큼이 됩니다.
    
    
  • 다만, 모든 재귀를 다 돌리면 O(4^N)이 되므로 N이 커질 경우 비효율적입니다.
  • z 이동 연산을 호출할때마다 이동 횟수는 N✗N이 됩니다. 또한, 찾으려는 점은 호출하려는 4가지 위치 중 한 곳에만 위치하므로, 해당 점의 위치에 해당하는 부분만을 재귀적으로 호출하게 하고 이전 이동횟수는 이미 진행했다고 보고 N✗N을 더해주면 O(N)으로 답을 구할 수 있습니다.

[ 🤟🏻 Code ] from ss-won

#include <iostream>
#include <cmath>
using namespace std;
int N, r, c, res = 0;
bool answer = false;
pair<int,int> mv[4] = {{0,0}, {0,1}, {1,0}, {1,1}};

void movez(int size, int sx, int sy){
    if(size == 2){
        for(int i=0;i<4;i++){
            int cx = sx + mv[i].first, cy = sy + mv[i].second;
            if(cx == r && cy == c){
                cout << res;
                answer = true;
                return;
            }
            res++;
        }
    }
    else{
        for(int i=0;i<4;i++){
            if(answer) break;
            int nexts = size/2, nx = sx+mv[i].first*nexts, ny = sy+mv[i].second*nexts;
            if(r >= nx && r < nx + nexts && c >= ny && c < ny + nexts)
                movez(nexts, nx, ny);
            else
                res += nexts * nexts;
        }
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> r >> c;
    // pow 연산은 double을 기준으로 하기 때문에, 오차가 생길 수 있어서
    // int 제곱 연산에서는 사용을 지양하는것이 좋다고 합니다.
    movez((int)pow(2.0,N), 0, 0);
    return 0;
}