백준 14956번 Philosopher's Walk

문제 링크입니다: https://www.acmicpc.net/problem/14956

문제에서 나오는 모양을 Hilbert Curve라고 합니다.

Hilbert Curve에 관해서는 http://datagenetics.com/blog/march22013/index.html에 잘 나와있습니다.

기존의 쿼드트리(http://jaimemin.tistory.com/1072) 문제처럼 분할정복을 이용해 재귀호출을 하면 되는 문제였지만 우하단이 계산하기 매우 까다로운 문제였습니다.

자세한 내용을 쓰기보다는 직접 코드를 확인하는 것이 훨씬 도움될 것 같습니다!

(https://baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/401)님의 코드가 많은 도움이 됐습니다!

#include <iostream>

#include <algorithm>

using namespace std;

 

pair<int, int> hilbert(int N, int M)

{

        pair<int, int> p;

        //기저 사례: W1

        if (N == 2)

        {

                 switch (M)

                 {

                 case 0:

                         p = { 1, 1 };

                         return p;

                 case 1:

                         p = { 1, 2 };

                         return p;

                 case 2:

                         p = { 2, 2 };

                         return p;

                 case 3:

                         p = { 2, 1 };

                         return p;

                 }

        }

 

        int half = N / 2;

        int quadrant = M / (half*half);

        switch (quadrant)

        {

        //좌하단

        case 0:

                 p = hilbert(half, M % (half*half));

                 swap(p.first, p.second);

                 return p;

        //좌상단

        case 1:

                 p = hilbert(half, M % (half*half));

                 p.second += half;

                 return p;

        //우상단

        case 2:

                 p = hilbert(half, M % (half*half));

                 p.first += half;

                 p.second += half;

                 return p;

        //우하단

        case 3:

                 p = hilbert(half, M % (half*half));

                 pair<int, int> temp = { 2 * half - p.second + 1, half - p.first + 1 };

                 return temp;

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, M;

        cin >> N >> M;

 

        //0부터

        pair<int ,int> result = hilbert(N, M - 1);

        cout << result.first << " " << result.second << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~