[백준] 1074번 Z

Z(https://www.acmicpc.net/problem/1074)

---

1. 이해하기

• Z모양으로 배열을 탐색한다.
• 배열을 만들기에는 메모리 공간이 충분하지 않다.
• 재귀적으로 4등분한 후 Z모양에 따라 순서대로 맞는지 찾아본다.

---

2. 구현하기

• solve(x,y,n): 현재위치 (x,y), 현재 배열의 크기가 2의 n승.

  • 만약 n의 크기가 1이라면 Z모양으로 탐색하면서 알고자 하는 위치인지 알아본다.
  • 배열을 4등분한 후 다시 탐색한다.

  void solve(int x, int y, int n) {
      if(ans != -1) return;
      if(n == 1) {
          if(x == r and y == c) ans = cnt;
          cnt++;
          if(x == r and y+1 == c) ans = cnt;
          cnt++;
          if(x+1 == r and y == c) ans = cnt;
          cnt++;
          if(x+1 == r and y+1 == c) ans = cnt;
          cnt++;
          return;
      }
      for(int i = 0; i < 2; i++) {
          for(int j = 0; j < 2; j++) {
              solve(x+(1<<(n-1))*i, y+(1<<(n-1))*j,n-1);
          }
      }
  }

  • 여기서 2의 n승을 구할때 비트마스크를 사용하면 시간을 절반가까이 단축시킬 수 있다.
  • 아마 4등분을 할 때 반복문을 이용하지 않으면 시간을 더 단축시킬 수 있을 것 같다.

---

3. 전체코드

#include <iostream>
using namespace std;

int N,r,c;
int cnt,ans=-1;

void solve(int x, int y, int n) {
    if(ans != -1) return;
    if(n == 1) {
        if(x == r and y == c) ans = cnt;
        cnt++;
        if(x == r and y+1 == c) ans = cnt;
        cnt++;
        if(x+1 == r and y == c) ans = cnt;
        cnt++;
        if(x+1 == r and y+1 == c) ans = cnt;
        cnt++;
        return;
    }
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            solve(x+(1<<(n-1))*i, y+(1<<(n-1))*j,n-1);
        }
    }
}

int main() {
    cin >> N >> r >> c;
    solve(0,0,N);
    cout << ans << '\n';
}