[백준 1074번] Z

문제 설명

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

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

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

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

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

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

알고리즘

분할 정복(Divide and conquer), 재귀(Recursion)

접근 방식 및 풀이

간단한 문제이기 때문에 빨리 풀 수 있었다. 우선 Z 모양으로 되어 있기 때문에 4분위(좌상단, 우상단, 좌하단, 우하단)로 나누어 풀면 되겠다고 생각했다. 4분위 중 목적지가 속한 분위로 이동한다. 이 때, 이동할 분위보다 순서상 앞에 있는 분위만큼 이동 횟수를 늘려준다. 4번째 칸으로 이동할 경우 3칸만큼, 3번째 칸으로 이동할 경우 2칸만큼, 2번째 칸으로 이동할 경우 1칸만큼 늘려준다. 이동을 끝냈으면 이동한 분위의 첫번째 칸이 목적지인지 확인한다. 목적지가 아닐 경우 해당 분위를 Z 모양, 4분위로 나누고 위의 과정을 반복한다. 이렇게 반복하다가 목적지를 발견하면 그때의 이동 횟수를 출력한다.

코드

문제 풀이에 사용한 언어: C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long find(int start_row, int start_col);

int n, row, col;
long long n_th, length;

int
main(){
    n_th = 0;
    scanf("%d %d %d", &n, &row, &col);
    length = (long long)pow(2, n);
    printf("%lld\n", find(0, 0));
    return 0;
}

// 현재 위치가 목적지인지 확인하고 아니라면 4분위 중 이동해야할 곳으로 이동
long long find(int currentRow, int currentCol){
    if(currentRow == row && currentCol == col){ // 현재 위치가 목적지라면
        return n_th; // 몇번째인지 출력
    }
    length /= 2;
    if(row >= currentRow + length && col >= currentCol + length){ // 4분위
        n_th += length * length * 3; // 4번째 칸이므로 3칸을 넘긴다.
        return find(currentRow + length, currentCol + length); // 해당 부분의 첫번째 위치에서 찾기
    }
    else if(row >= currentRow + length){ // 3분위
        n_th += length * length * 2; // 3번째 칸이므로 2칸을 넘긴다.
        return find(currentRow + length, currentCol); // 해당 부분의 첫번째 위치에서 찾기
    }
    else if(col >= currentCol + length){ // 2분위
        n_th += length * length; // 2번째 칸이므로 1칸을 넘긴다.
        return find(currentRow, currentCol + length); // 해당 부분의 첫번째 위치에서 찾기
    }
    else { // 1분위
        return find(currentRow, currentCol); // 해당 부분의 첫번째 위치에서 찾기
    }
}