[BOJ] 14956_Philosopher's walk with cpp

# 생각

문제에 나오는 모양은 Hilbert Curve 모양으로

쿼드트리와 같은 분할정복 재귀문제와 동일한 방법으로 풀 수 있다

 

base condition은 가장 작은 사각형의 길이가 2^1이기 때문에

side가 2일때 4가지로 나누어 반환해주면 된다

 

재귀식은 절반씩 나누어 4개의 사각형으로 함수를 호출해준다

walk를 사각형의 크기로 나누어 각각의 사분면에 맞는 함수를 호출하고 반환해준다

case 0부터 시작하기 때문에 함수 호출시 (walk-1)을 넣어줬다

 

단, 각 사분면과 그 모양에 따른 좌표값을 반환해야하므로 주의해야 한다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;
// R : 0.5s, 512MB
// N = 2^k, M = 2^2k (0 < k <= 15)
pair<int, int> HilbertCurveRecursive(int side, int walk)
{
	// 가장 작은 사각형의 길이는 N = 2^1
	if (side == 2)
	{
		switch (walk)
		{
		case 0:
			return { 1,1 };
		case 1:
			return { 1,2 };
		case 2:
			return { 2,2 };
		case 3:
			return { 2,1 };
		default:
			cout << "unknown type" << walk << '\n';
			break;
		}
	}

	int half = side * 0.5;
	int quadrant = (half * half);

	pair<int, int> coord;
	switch (walk / quadrant)
	{
	case 0:	// quadrant 3
		coord = HilbertCurveRecursive(half, walk % quadrant);
		return { coord.second, coord.first };
	case 1:	// quadrant 2
		coord = HilbertCurveRecursive(half, walk % quadrant);
		return { coord.first, coord.second + half };
	case 2:	// quadrant 1
		coord = HilbertCurveRecursive(half, walk % quadrant);
		return { coord.first + half, coord.second + half };
	case 3:	// quadrant 4
		coord = HilbertCurveRecursive(half, walk % quadrant);
		return { 2 * half - coord.second + 1, half - coord.first + 1};
	default:
		cout << "unknown type" << walk / quadrant << '\n';
		break;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int side, walk;
	cin >> side >> walk;
	pair<int, int> ans = HilbertCurveRecursive(side, walk - 1);
	cout << ans.first << ' ' << ans.second;
}

 

---

https://www.acmicpc.net/problem/14956

14956번: Philosopher’s Walk