[백준 - 14956] Philosopher’s Walk - C++

분류: 재귀, 좌표 계산 /

 

문제

문제 링크

문제 설명

In Programming Land, there are several pathways called Philosopher’s Walks for philosophers to have a rest. A Philosopher’s Walk is a pathway in a square-shaped region with plenty of woods. The woods are helpful for philosophers to think, but they planted so densely like a maze that they lost their ways in the maze of woods of a Philosopher’s Walk.

Fortunately, the structures of all Philosopher’s Walks are similar; the structure of a Philosopher’s Walk is designed and constructed according to the same rule in a 2^k meter square. The rule for designing the pathway is to take a right-turn in 90 degrees after every 1-meter step when k is 1, and the bigger one for which the integer k is greater than 1 is built up using four sub-pathways with k - 1 in a fractal style. Figure F.1 shows three Philosopher’s Walks for which k is 1, 2, and 3. The Philosopher’s Walk W₂ consists of four W₁ structures with the lower-left and the lower-right ones are 90 degree rotated clockwise and counter-clockwise, respectively; the upper ones have the same structure with W₁. The same is true for any W_k for which the integer k is greater than 1. This rule has been devised by a mathematical philosopher David Hilbert (1862 – 1943), and the resulting pathway is usually called a HILBERT CURVE named after him. He once talked about a space filling method using this kind of curve to fill up a square with 2^k sides, and every Philosophers’ Walk is designed according to this method.

(a) W1	(b) W2	(c) W3

Figure F.1. Three Philosopher's Walks with size (a) 2¹ = 2, (b) 2² = 4, and (c) 2³ = 8, repectively.

Tae-Cheon is in charge of the rescue of the philosophers lost in Philosopher’s Walks using a hot air balloon. Fortunately, every lost philosopher can report Tae-Cheon the number of meter steps he has taken, and Tae-Cheon knows the length of a side of the square of the Philosopher’s Walk. He has to identify the location of the lost philosopher, the (x,y) coordinates assuming that the Philosopher’s Walk is placed in the 1st quadrant of a Cartesian plain with one meter unit length. Assume that the coordinate of the lower-left corner block is (1,1). The entrance of a Philosopher’s Walk is always at (1,1) and the exit is always (n,1) where n is the length of a side. Also assume that the philosopher have walked one meter step when he is in the entrance, and that he always go forward to the exit without back steps.

For example, if the number of meter-steps taken by a lost philosopher in the Philosopher’s Walk in W₂ in Figure F.1(b) is 10, your program should report (3,4).

Your mission is to write a program to help Tae-Cheon by making a program reporting the location of the lost philosopher given the number of meter-steps he has taken and the length of a side of the square of the Philosopher’s Walk. Hurry! A philosopher urgently needs your help.

입력

Your program is to read from standard input. The input consists of a single line containing two positive integers, n and m, representing the length of a side of the square of the Philosopher’s Walk and the number of meter-steps taken by the lost philosopher, respectively, where n = 2^k and m ≤ 2^2k for an integer k satisfying 0 < k ≤ 15.

출력

Your program is to write to standard output. The single output line should contain two integers, x and y, separated by a space, where (x,y) is the location of the lost philosopher in the given Philosopher’s Walk.

 

풀이

#include <iostream>
using namespace std;

int N, M, locX, locY;

void findLoc(int n, int m) {
    if(n == 2) { 
        locX = m < 2 ? 1 : 2;
        locY = (m == 0 || m == 3) ? 1 : 2;
        return;
    }
    n /= 2;
    findLoc(n, m % (n*n));
    switch (m / (n*n)) {
        int tmp;
        case 0:
            tmp = locX;
            locX = locY;
            locY = tmp;
            break;
        case 2:
            locX += n;
        case 1:
            locY += n;
            break;
        case 3:
            tmp = locY;
            locY = n + 1 - locX;
            locX = 2*n + 1 - tmp;
            break;
        default:
            throw;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    findLoc(N, M-1);
    cout << locX << ' ' << locY;
}

계산의 편의를 위해 `findLoc(N, M-1)`로 시작한다. `M-1`로 시작하면 몫 연산으로 사분면을 정할 수 있다.

if-else문 대신 switch문을 쓴 이유는 몫연산을 한번만하기 위해서다.

if-else문을 사용하면 매번 몫을 계산하거나 변수를 선언해야하는데 재귀함수 안에서 변수선언은 최대한 안하려고 한다.

 

알고리즘은 다음과같다.

1. `n = 2`일 때 `m`으로 좌표를 계산할 수 있다.
2. `n > 2`일 때, `n - 1`의 좌표를 계산할 수 있다면, 평행이동과 대칭이동으로 `n`의 좌표도 계산할 수 있다.

몫을 사분면 이름이라 하자.

0사분면은 `n - 1` 좌표에 y = x 대칭이동이다. 이 경우 x와 y를 스왑하면된다.

1사분면은 `n - 1` 좌표에 y축 +n/2 평행이동이다. (위 코드에서는 `n /= 2`를 했기 때문에 `locY += n`이다.)

2사분면은 `n - 1` 좌표에 y축, x축 +n/2 평행이동이다.

3사분면은 `n - 1` 좌표에 y = -x + n + 1 평행이동 후 y축 -n/2 대칭이동이다.

(a, b)를 y = -x + n + 1 대칭이동 한 좌표는 (n + 1 - b, n + 1 - a)다.