[백준] 1074번 : Z

문제

 

---

풀이

 

분할정복 문제다. 일단 그냥 판을 크게 4등분 한다면

1 2

3 4

이 순서로 방문해야 한다.

 

그러면 판을 계속 4등분 하면서 우리가 구하고자 하는 좌표가 존재하는 사분면만 탐색하면 될 것 같은데

함수에 들어갈 인자가 뭐가 있을까...

사람마다 다르겠지만 대충 이번에 탐색할 사분면을 A라고 하면 기본적으로 들어가는 N, r, c에 더해서

A의 가장 왼쪽 위 좌표와 해당 좌표를 방문하는 순서를 저장했다.

 

4등분 될 때마다 N은 1씩 줄어든다. N이 0이 될 때까지 탐색하면 될 것이다.

---

소스코드

 

#include <iostream>
#include <utility>
#include <cmath>
#include <vector>

using namespace std;

int recurZ(int N, int r, int c, int num, pair<int, int> p) {
    if (N == 0) //방문 순서 출력
        return num;
    int mul = pow(2, N - 1); //2^3 * 2^3 이라면 4씩 좌표가 증가할 것
    vector<pair<int, int>> pos; //각 사분면의 좌표
    for (int i = p.first; i <= (p.first + mul); i += mul) {
        for (int j = p.second; j <= (p.second + mul); j += mul)
            pos.push_back(make_pair(i, j));
    }
    for (int i = 3; i >= 0; i--) { //뒤에서부터 일치하는 해당하는 사분면 찾기
        if ((r >= pos[i].first) && (c >= pos[i].second))
            return recurZ(N - 1, r, c, num + (pow(4, N - 1) * i), pos[i]);
    }
    return 0;
}

int main() {
    int N, r, c;

    cin >> N >> r >> c;
    cout << recurZ(N, r, c, 0, make_pair(0, 0));
}

전체 소스코드다.

 

int recurZ(int N, int r, int c, int num, pair<int, int> p) {
    if (N == 0) //방문 순서 출력
        return num;
    int mul = pow(2, N - 1); //2^3 * 2^3 이라면 4씩 좌표가 증가할 것
    vector<pair<int, int>> pos; //각 사분면의 좌표
    for (int i = p.first; i <= (p.first + mul); i += mul) {
        for (int j = p.second; j <= (p.second + mul); j += mul)
            pos.push_back(make_pair(i, j));
    }
    for (int i = 3; i >= 0; i--) { //뒤에서부터 일치하는 해당하는 사분면 찾기
        if ((r >= pos[i].first) && (c >= pos[i].second))
            return recurZ(N - 1, r, c, num + (pow(4, N - 1) * i), pos[i]);
    }
    return 0;
}

이 부분을 자세히 설명하자면...

 

    int mul = pow(2, N - 1); //2^3 * 2^3 이라면 4씩 좌표가 증가할 것
    vector<pair<int, int>> pos; //각 사분면의 좌표
    for (int i = p.first; i <= (p.first + mul); i += mul) {
        for (int j = p.second; j <= (p.second + mul); j += mul)
            pos.push_back(make_pair(i, j));
    }

N=3이라고 해보자 그럼 8x8의 행렬이 나온다. 이걸 4등분하고 각각의 가장 왼쪽 위 좌표를 구하면

(0, 0) (0, 4)

(4, 0) (4, 4)

가 나온다.

 

2^(N-1)만큼 좌표가 증가하는 것인데...그래서 4등분한 좌표 4개를 pos 벡터에 넣어준다.

근데 엄밀히 말하면 처음에나 (0, 0)으로 시작하는거지 재귀를 하다보면 (4, 0)에서 시작할 수도 있고 암튼 그렇다.

그래서 해당 행렬의 왼쪽 위 좌표인 p가 인자로 있는 것이고 pos 벡터를 채울 때 이걸 사용한다.

 

    for (int i = 3; i >= 0; i--) { //뒤에서부터 일치하는 해당하는 사분면 찾기
        if ((r >= pos[i].first) && (c >= pos[i].second))
            return recurZ(N - 1, r, c, num + (pow(4, N - 1) * i), pos[i]);
    }

그리고 r, c가 들어있을 사분면을 찾는데

1 2

3 4

에서 1->2->3->4로 찾는게 아니라 4->3->2->1로 찾을 것이다.

지금 내가 작성한 코드라면 1->2->3->4로 탐색을 진행할 때,

(5, 5) 같은 좌표가 (0, 0), (0, 4), (4, 0), (4, 4) 모두에 재귀 호출을 할 것이다. 그래서 반대로 탐색하는 것이다.

 

아무튼 해당하는 사분면을 찾으면 N-1을 하고, pos[i]를 왼쪽위 좌표로 넘기고

해당 좌표의 방문 순서인 num도 갱신해서 넘겨주는데 이건 알아서 계산하시길...이 부분은 그냥 수학이다...

 

    if (N == 0) //방문 순서 출력
        return num;

N이 0이 되면 num을 반환하면 되겠다.

재귀함수는 설명이 너무 어렵다...