[C++] 백준 1074번: Z

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

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

출력

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

풀이

분할 정복 알고리즘을 사용하는 문제로, 2^n * 2^n 크기의 2차원 배열을 4등분하여

r행 c열이 포함되어있지 않은 분면은 필요가 없으므로 cnt에 더해주고 포함된 분면을 재귀적으로 나눠주며 몇번째로 방문하는지 계산한다.

소스코드

   #include <iostream>
   #include <algorithm>
   #include <vector>
   #include <string>
   #include <math.h>
   #include <queue>
   /*
   * 분할 정복을 이용한 2차원 배열에서 해당 좌표 찾기
   */
   using namespace std;

   int n, r, c;
   int cnt;
   void divide(int x, int y, int n) {
       if (x == c && r == y) {
           cout << cnt;
           return;
       }
       if (x + n <= c || y + n <= r || r < y || c < x) {
           cnt += n * n;
           return;
       }
       else {
           divide(x, y, n / 2);
           divide(x + n / 2, y, n / 2);
           divide(x, y + n / 2, n / 2);
           divide(x + n / 2, y + n / 2, n / 2);
       }
   }

   int main(void)
   {
       cin.tie(NULL);
       ios::sync_with_stdio(false);
       cin >> n >> r >> c;
       divide(0, 0, (1 << n)); // 1 << n 비트연산을 하면 2의n승이 된다.

       return 0;
   }