백준 5405, 프랙탈 거리

개요

문제 링크
골드 1, 분할정복, 재귀
힐베르트 곡선으로 프랙탈 모양을 만들었을 때, h,o번째 점 사이의 거리 구하기

---

접근

1. 이런 식의 4분할을 통한 분할정복은 머리가 엄청 아프다. 머리가 좋은 편이 아니라 시간도 느리게 짜고 푸는데 엄청 오래걸렸다.

2. 설명할 게 엄청 많은데, 순서를 매겨보자면 이렇다.

   1. 가장 큰 사각형에서, 현재 점이 속한 사분면을 선택한다.
   2. 현재 사분면의 도형의 입구의 방향을 구해야 한다.
   3. 현재 사분면이 집을 셀 때, 입구를 기준으로 오른쪽 가지에서 출발하는지, 혹은 왼쪽 가지에서 출발하는지 확인해야 한다.

3. 각각은 코드에서 position (p), hole (h), branch (b)라는 변수명을 사용했다. 이제 하나씩 알아보자. 먼저 사분면 구하기, 사분면은 우리가 아는 방식대로 1,2,3,4분면이 아니라, 집을 세는 순서대로 구해줘야 한다.
   이게 무슨소린가 하니, 아래 그림을 잘 보자.

   

   (예제 그림인데 7,8번 번호가 잘못매겨져 있어서 그냥 그렸다.)
   전체 모양은 왼쪽에 구멍이 있다. (hole = L)
   출발 방향은 구멍의 오른쪽에 있는 가지이다. (branch = R)
   9번을 잘 보자. 몇 사분면에 있는가 하니 3번째 사분면에 있다. (position=2)

4. 위 그림에서 다음 단계로 넘어가는 과정에 필요한 정보를 생각해보자.
   여기서 다음 단계란 9번이 속해있는 n=1일때의 도형인데, 왼쪽에 구멍이 있는 n=2 도형의 오른쪽 가지에서 출발해 도달한 3번째 사분면이다. 이때 다음 단계는 마찬가지로, 왼쪽에 구멍이 있는 n=1 도형의 오른쪽 가지에서 출발해 도달한 1번째 사분면이다.

   말이 헷갈리니 14번을 보자. 14번은 (n=2 왼구멍, 오른쪽가지, 4번째) -> (n=1 아래구멍, 왼쪽가지, 2번째) 를 통해 저 위치에 도착한다.

5. 자 그럼 10번을 구해보자. 10번은 (세로,가로)=(2,3)의 위치에 있다. (2,3)=(2,2)+(0,1)로 쪼개줄 수 있는데, (2,2)는 무엇이냐, n=2인 도형의 3사분면의 출발점이다. 따라서 재귀적으로 크기를 줄여가며 작은 사분면의 출발점의 위치를 더해주면 된다. 일종의 lower threshold를 추가해 주는 것이다.

6. 사분면을 구해 출발점의 위치를 더하면 다음 단계에 대한 정보를 재귀적으로 넘겨줘야 한다. 먼저 다음단계의 구멍이다. 그림에서 (Left hole, Right branch)의 경우는 다음 단계의 구멍이 (ULLD)와 같이 되는 것을 볼 수 있는데, 이걸 hole과 branch에 따라 정리해주면 다음과 같다.

   // next_hole
   (L,L) -> DLLU, (L,R) -> ULLD
   (U,L) -> LUUR, (U,R) -> RUUL
   (R,L) -> URRD, (R,R) -> DRRU
   (D,L) -> RDDU, (D,R) -> UDDR

   이때 branch의 방향을 잘 고려하면 차원을 하나 줄일 수 있다. branch가 right이면, 뒤집어서 3-사분면 번째 next_hole을 선택한다. 잘 생각해보면 위의 그림에서 왼쪽 가지에서 출발해 16부터 1까지 반대로 간다 생각했을 때 순서대로 DLLU를 따른다.

   if (branch == right)
       next_position = 3-next_position
   next_hole = next[current_hole][next_position]

7. 다음은 branch의 방향이다. 위의 그림에서 (Left hole, Right branch)의 다음단계의 branch는 (LRRL) 이 되는 것을 알 수 있다. 이때는 반대로 출발하면 RLLR이 된다.

   // next_branch
   (L,L) -> RLLR, (L,R) -> LRRL
   (U,L) -> RLLR, (U,R) -> LRRL
   (R,L) -> RLLR, (R,R) -> LRRL
   (D,L) -> RLLR, (D,R) -> LRRL

   그런데 이게 웬일이람. Hole의 방향에 관계없이 다음 단계의 출발 가지는 RLLR이다. 사실 회전한 것이기 때문에 당연하다. 그래서 next branch는 아래와 같이 구해준다.

   next_branch = next[next_position]
   if (branch == right)
       next_branch = !next_branch
       // L->R,  R->L

8. 마지막으로 threshold, 이것도 일반 XY평면에서 처럼 작동하면 좋겠지만, branch, hole의 방향에 따라 모두 다르다.

   위의 그림에서 보면 (Left hole, Right branch)에서 threshold는 ((0,0),(0,s),(s,s),(s,0))이 된다. (s=size) 순서대로 왼위, 오위, 오아래, 왼아래인 것이다. 이것도 정리해주면 다음과 같다.

   (L,L) -> {{s,0},{s,s},{0,s},{0,0}}
   (L,R) -> {{0,0},{0,s},{s,s},{s,0}}
   
   (U,L) -> {{0,0},{s,0},{s,s},{0,s}}
   (U,R) -> {{0,s},{s,s},{s,0},{0,0}}
   
   (R,L) -> {{0,s},{0,0},{s,0},{s,s}}
   (R,R) -> {{s,s},{s,0},{0,0},{0,s}}
   
   (D,L) -> {{s,s},{0,s},{0,0},{s,0}}
   (D,R) -> {{s,0},{0,0},{0,s},{s,s}}

   다른 변수와 마찬가지로 branch의 방향에 대해 대칭성을 가진다. 이렇게 구해주면 된다.

   // threshold
   if (branch == right)
       next_position = 3-next_position
   threshold = next[current_hole][next_position]

9. 마지막으로 구현을 위해 hole은 LURD -> 0123, branch는 LR -> 01로 설정해주면 된다. 사이즈는 얼마나 줄이냐? 하면 4씩 나눠주면 된다. 그리고 threshold의 좌표는 전체크기의 제곱근만큼이다.
   아마 더 쉽고 빠르게 구현한 사람들도 있을텐데 나는 이게 한계인 듯 싶다..

---

Pseudo code

pos (cur, n, hole, branch) {
    next_position = (cur/(2^n))%4

    if (branch)
        next_position = 3 - next_position
    next_hole = next[hole][next_position]

    next_branch = next[next_position]
    if (branch)
        next_branch = !next_branch

    threshold = next[hole][next_position]

    next_cur = cur - next_position*(2^n)

    next_pos = pos(next_cur, n-2, next_hole, next_branch)
    return threshold + next_pos
}

---

Source code

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

using ld = long long;
typedef struct pii {
    ld h, w;
    pii operator + (pii a) {
        return {h+a.h,w+a.w};
    };
} pii;

ld con[4][4] = {
    {3,0,0,1},{0,1,1,2},{1,2,2,3},{2,3,3,0}
};

ld dir[4] = {1,0,0,1};

pii get(ld s, ld p, ld h) {
    ld e = 1<<(s/2);
    pii a[4][4] = {
        {{e,0},{e,e},{0,e},{0,0}},
        {{0,0},{e,0},{e,e},{0,e}},
        {{0,e},{0,0},{e,0},{e,e}},
        {{e,e},{0,e},{0,0},{e,0}}
    };
    return a[h][p];
}

pii pos(ld n, ld s, ld h, ld b) {
    if (s<0) return {0,0};
    ld e = 1<<s;
    ld p = (n/e)%4;
    ld np = b?3-p:p;
    ld nh = con[h][np];
    ld nb = b?!dir[p]:dir[p];
    return get(s,np,h)+pos(n-p*e,s-2,nh,nb);
}

ld test() {
    ld n, h, o;
    cin >>n>>h>>o;
    n = (n-1)*2;
    pii ph = pos(h-1,n,0,1);
    pii po = pos(o-1,n,0,1);

    double dw, dh;
    dw = 10*abs(ph.w-po.w);
    dh = 10*abs(ph.h-po.h);
    return round(sqrt(dw*dw+dh*dh));
}

int main() {
    ld t;
    cin >> t;
    while (t--)
        cout << test() << "\n";
}