[백준/BOJ] 1074 Z / C++

Kwaaaaan·2023년 8월 8일

알고리즘

목록 보기

2/5

문제

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

N > 1인 경우, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

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

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

제한
1 ≤ N ≤ 15
0 ≤ r, c < 2N

예제 입력 1
2 3 1
예제 출력 1
11
예제 입력 2
3 7 7
예제 출력 2
63
예제 입력 3
1 0 0
예제 출력 3
0
예제 입력 4
4 7 7
예제 출력 4
63
예제 입력 5
10 511 511
예제 출력 5
262143
예제 입력 6
10 512 512
예제 출력 6
786432

입출력 예

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

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

풀이

저는 기본적으로 재귀를 이용한 방법과 좌표를 탐색하는 식의 방법으로 문제를 풀었습니다. 밑에 코드내용을 일단 먼저 확인하겠습니다.

#include <iostream>
#include <cmath>
using namespace std;

int processcion(int n, int x, int y) 
{
    int result = 0;
    int size = 1;

    for (int i = 0; i < n; i++) 
    {
        int square_size = pow(size, 2);

        int x_bit = (x / size) % 2;
        int y_bit = (y / size) % 2;

        int position = x_bit * 2 + y_bit;
        result += position * square_size;

        size *= 2;
    }

    return result;
}

int main() 
{
    int n, x, y;
    cin >> n >> x >> y;

    int result = processcion(n, x, y);
    cout << result << endl;

    return 0;
}

코드해석

processcion이라는 함수의 매개변수가 왜 3개일지를 먼저 생각해본다면, 기본적으로 2차원 평면상에는 x축과 y축이 존재합니다. 또한 2차원 평면의 크기를 설정해 주기 위해 n을 이용해 크기를 설정합니다. 또한, processcion함수는 정수형으로 선언해놓았습니다. processcion함수의 좌표 (x, y)가 몇번째로 방문하여 이를 계산해 반환하기 위해서 int형으로 선언하였습니다.