[BOJ] 1074번: Z

https://www.acmicpc.net/problem/1074

1074번: Z

문제

한수는 크기가 2^N× 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

 

---

풀이

📌 분할정복 + 재귀

배열을 4등분으로 나누고 원하는 좌표의 위치를 판단하여 해당 사분면으로 이동한다. 이를 재귀 함수를 이용하여 반복하다 보면 좌표의 위치를 발견할 수 있다. 

 

코드

#include <iostream>
using namespace std;

int n, c, r;
int ans = 0;
int s; 

void visit(int x, int y, int a) {
  if (x == r && y == c) {
    cout << ans << "\n";
    return;
  }

  if(x+a/2 > r && y+a/2 > c) {
    visit(x, y, a/2);  // 1사분면
  }
  else if(x+a/2 > r && y+a/2 <= c) {
    ans += (a/2)*(a/2);
    visit(x, y+a/2, a/2);  // 2사분면
  }
  else if(x+a/2 <= r && y+a/2 > c) {
    ans += (a/2)*(a/2)*2;
    visit(x+a/2, y, a/2);  // 3사분면
  }
  else {
    ans += (a/2)*(a/2)*3;
    visit(x+a/2, y+a/2, a/2);  // 4사분면
  }

  return;

}

int main() {
  int n;
  cin >> n >> r >> c;
  s = 1 << n;  // 1을 왼쪽으로 n비트만큼 이동 (2^n)
  visit(0, 0, s);
  return 0;
}

결과