[100] C++(Cpp) 백준 1074번: Z 문제 (분할정복, 재귀)

문제

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

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

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

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

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

입력

첫째 줄에 정수 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

 

 

 

 

<풀이>

https://hagisilecoding.tistory.com/14

백준 1074 Z c++ [컴공과고씨]

위의 풀이 방법을 참고하였음

 

이 문제는 분할정복과 재귀를 이용하여 해결하는 문제이다.

 

예를들어 큰 정사각형이 있다고 하자.

1	1	2
	3	4
3	4

위와 같이 4개의 사분면으로 분할할 수 있다.

다시, 4개의 각 사분면들은 다시 4개의 사분면으로 분할할 수 있다.

이렇게 계속 반복하면서 최소 단위 까지 분할하면서 주어진 행,열에 오기까지 방문한 칸의 수를 더해주면 된다.

 

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

    else if (c < x+size && r < y+size && c >= x && r >= y){ // 찾는 행, 열이 사분면 안에 존재할 경우
        visit(x, y, size/2); // 1사분면
        visit(x+size/2, y, size/2); // 2사분면
        visit(x, y+size/2, size/2); // 3사분면
        visit(x+size/2, y+size/2, size/2); // 4사분면
    }

    else ans += size * size; // 해당 사분면에 속해있지 않으면 size*size (이후의 사분면에 있다.)
}

재귀함수 코드이다.

(x, y)는 탐색하는 사각형의 왼쪽 위 모서리 좌표이다.

찾는 행과 열이 탐색하는 사각형 안에 존재할 경우엔 1, 2, 3, 4분면 순서대로 탐색해야한다. (찾는 행과 열 뒤 부분의 크기가 더해질수도 있음)

찾는 행과 열이 탐색하는 사각형 안에 존재하지 않는다면, ans += size * size 해준다.

이렇게 탐색하다가 x == c && y == r을 만족하면 ans를 출력한다.

 

 

 

<제출한 코드>

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

int N, r, c;
int ans = 0;

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

    else if (c < x+size && r < y+size && c >= x && r >= y){ // 찾는 행, 열이 사분면 안에 존재할 경우
        visit(x, y, size/2); // 1사분면
        visit(x+size/2, y, size/2); // 2사분면
        visit(x, y+size/2, size/2); // 3사분면
        visit(x+size/2, y+size/2, size/2); // 4사분면
    }

    else ans += size * size; // 해당 사분면에 속해있지 않으면 size*size (이후의 사분면에 있다.)
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> r >> c;

    visit(0, 0, pow(2, N)); // (0, 0) 사각형 왼쪽 위 좌표
    
    return 0;
}