백준 1074번 Z (C++)

알고리즘 공부 1주차 - 재귀함수

재귀함수에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천. 

알고리즘 공부 1주차(01): 재귀함수 개념

알고리즘 공부 1주차(01): 재귀함수 개념

백준 1074번 Z

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

1074번: Z

문제

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

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

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

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

 

---

문제 설명

이 문제는 앞선 그림에서도 볼 수 있듯이 Z 씩 전체 구역을 나눌 수 있다. 

n이 2이고 4x4 배열일 경우 

또한 이 상황에서 같은색 한칸을 가져와 또 다시 4칸으로 나눌 수 있다. 

이런식으로 나타낼 수 있다는 것이다. 

이걸 다른말로 하면 분할정복이라고 하는데, 커다란 문제를 여러 작은 문제들로 나누어 문제를 해결하고 이를 다시 합치는 것이다. 

우리는 지금 재귀함수를 응용하는 것이니 저 커다란 네모 하나를 구성하는 함수를 만들어주고, 그것을 각 상황에 따라 또 나누어 다시 호출하면 된다.

저 짙은 주황색부분까지 가는 경로는 파란색부분넓이 + 노란색부분넓이 + 주황색 부분의 나머지 넓이를 계산한 값이기 때문이다. 

그럼 어떻게 코딩을 통해 제 4분면을 만들 수 있는지 살펴보자.

우리가 일반적으로 생각하는 수학의 중심점은 위와 같지만

컴퓨터에서의 시작점(중심지)는 왼쪽 위이다. 

우리가 처음 생각한 n은 커다란 네모이고 우리가 구하고자 하고 있는 n은 정확히는 n/2이다.

시작점을 (x,y)로 잡았을때를 기준으로 보면

각 좌표는 위와 같이 나타낼 수 있다. 여기서 지금 x는 행, y는 열이므로 기저조건은 x==r && y==c 이다.

 

정리하자면 다음과 같이 4분면을 만들었을때

1. r,c가 현재 x+n,y+n의 범위 내에 있는지 확인한다.

2. r,c가 1번을 충족하고, x,y보다 크거나 같다면 재귀함수를 호출한다.

3. 1,2번을 충족하지 않는다면 cn값을 정사각형의 넓이만큼 더해준다. (cn의 초기값은 0) 

---

제출한 코드(c++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int n;
int cn = 0;
void z(int x, int y, int n, int r, int c) {
    if (y == c && x == r) {//r c와 같아지면 출력
        cout << cn << "\n";
        return;
    }
    else if (c < y + n && r < x + n && c >= y && r >= x)
    {//범위 확인
        z(x,y, n / 2, r, c);//2사분면
        z(x,y + n / 2, n / 2, r, c);//1사분면
        z(x + n / 2, y, n / 2, r, c);//3사분면
        z(x + n / 2, y + n / 2, n / 2, r, c);//4사분면
    }
    else {
        cn += n * n;//카운트는 정사각형의 넓이
        //printf("%d ", cn);
    }

}
int main(void) {
    cin >> n;
    int r = 0, c = 0;
    cin >> r >> c;
    z(0, 0, pow(2, n), r, c);

    return 0;
}