백준 - Philosopher’s Walk (14956)

1. 문제

문제 링크

설명
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 2k 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 W2 consists of four W1 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 W1. The same is true for any Wk 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 2k sides, and every Philosophers’ Walk is designed according to this method.

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 W2 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 = 2k and m ≤ 22k 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.

2. 풀이

요약하면 철학자가 n x n 크기의 철학자의 미로에서 m 걸음 가다가 길을 잃었는데,
어느 좌표에 있는지 알아내는 문제입니다.

문제의 사진을 보면 미로의 규칙을 찾을 수 있습니다.
n x n 크기의 미로는 (n - 1) x (n - 1) 크기의 미로 4개로 이루어져 있는데요.

• 미로가 똑바로 서있을 때
  • 1사분면은 (n - 1) x (n - 1)이 그대로 있는 모양
  • 2사분면은 (n - 1) x (n - 1)이 그대로 있는 모양
  • 3사분면은 (n - 1) x (n - 1)이 오른쪽으로 누운 모양
  • 4사분면은 (n - 1) x (n - 1)이 왼쪽으로 누운 모양
• 미로가 오른쪽으로 누워있을 때
  • 1사분면은 (n - 1) x (n - 1)이 오른쪽으로 누운 모양
  • 2사분면은 (n - 1) x (n - 1)이 아래로 뒤집어진 모양
  • 3사분면은 (n - 1) x (n - 1)이 그대로 있는 모양
  • 4사분면은 (n - 1) x (n - 1)이 오른쪽으로 누운 모양
• 미로가 아래로 누워있을 때
  • 1사분면은 (n - 1) x (n - 1)이 왼쪽으로 누운 모양
  • 2사분면은 (n - 1) x (n - 1)이 오른쪽으로 뒤집어진 모양
  • 3사분면은 (n - 1) x (n - 1)이 아래로 뒤집어진 모양
  • 4사분면은 (n - 1) x (n - 1)이 아래로 뒤집어진 모양
• 미로가 왼쪽으로 누워있을 때
  • 1사분면은 (n - 1) x (n - 1)이 아래로 뒤집어진 모양
  • 2사분면은 (n - 1) x (n - 1)이 왼쪽으로 누운 모양
  • 3사분면은 (n - 1) x (n - 1)이 왼쪽으로 누운 모양
  • 4사분면은 (n - 1) x (n - 1)이 그대로 있는 모양

이러한 규칙을 찾을 수 있습니다.
우리는 위 규칙을 이용해서 철학자가 어느 좌표에 있는지 재귀적으로 찾을 수 있게 됩니다.
예시로 아래의 사진과 같이 4 x 4 크기의 미로에서 12걸음을 가다가 길을 잃었다고 합시다.

우리는 1사분면에서 길을 잃었다는 사실을 알기 때문에
굳이 3사분면 ~ 2사분면을 거쳐 1사분면까지 탐색할 필요가 없습니다.
바꿔말하면 2 x 2 크기의 미로에서 4걸음을 가다가 길을 잃은 문제로 좁힐 수 있는 겁니다.
다시 2 x 2 크기의 미로로 좁혀서 생각해보면
철학자는 4사분면에 있다는 사실을 알 수 있고 그 해당 좌표를 리턴하면 답이 됩니다.

3. 전체 코드

#include <iostream>

using namespace std;

pair<int, int> slove(int n, int m, int r, int c, int d) {
	if (n == 1) return { r, c };

	n /= 2;
	int area = n * n;

	if (d == 0) { // 미로가 똑바로 서있을 때
		if (1 <= m && m <= area) return slove(n, m, r, c, 1);
		if (area < m && m <= 2 * area) return slove(n, m - area, r + n, c, 0);
		if (2 * area < m && m <= 3 * area) return slove(n, m - 2 * area, r + n, c + n, 0);
		return slove(n, m - 3 * area, r + n - 1, c + 2 * n - 1, 3);
	}

	if (d == 1) { // 미로가 오른쪽으로 누워있을 때
		if (1 <= m && m <= area) return slove(n, m, r, c, 0);
		if (area < m && m <= 2 * area) return slove(n, m - area, r, c + n, 1);
		if (2 * area < m && m <= 3 * area) return slove(n, m - 2 * area, r + n, c + n, 1);
		return slove(n, m - 3 * area, r + 2 * n - 1, c + n - 1, 2);
	}

	if (d == 2) { // 미로가 아래로 뒤집어져 있을 때
		if (1 <= m && m <= area) return slove(n, m, r, c, 3);
		if (area < m && m <= 2 * area) return slove(n, m - area, r - n, c, 2);
		if (2 * area < m && m <= 3 * area) return slove(n, m - 2 * area, r - n, c - n, 2);
		return slove(n, m - 3 * area, r - n + 1, c - 2 * n + 1, 1);
	}
    
	// 미로가 왼쪽으로 누워있을 때
	if (1 <= m && m <= area) return slove(n, m, r, c, 2);
	if (area < m && m <= 2 * area) return slove(n, m - area, r, c - n, 3);
	if (2 * area < m && m <= 3 * area) return slove(n, m - 2 * area, r - n, c - n, 3);
	return slove(n, m - 3 * area, r - 2 * n + 1, c - n + 1, 0);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
    
    int N, M;
    
	cin >> N >> M;

	pair<int, int> p = slove(N, M, 1, 1, 0);

	cout << p.second << ' ' << p.first;
	return 0;
}