[BOJ 1074] Z

이 문제는 이곳에서 확인할 수 있습니다.

이 문제는 2^N x 2^N의 배열을 Z 모양으로 방문하여 (r, c) 위치의 칸에는 몇번 째로 도착하는지 구하는 문제입니다.

가장 직관적인 방법은 (0, 0) 부터 시작해 (r, c)가 나올 때 까지 방문하는 것입니다.
하지만 N은 15까지이고 칸의 수는 2^15 x 2^15 이기 때문에 모든 칸을 방문하여 문제를 해결할 순 없습니다. 그러므로 조건에 맞는 칸만 방문하여 최적화를 해주어야 합니다.

문제에서 동일한 패턴을 가지고 배열을 방문하기 때문에 분할 정복으로 문제를 해결할 수 있습니다.

N = 2, r = 3, c = 2

구하고자 하는 (r, c)의 사분면 위치를 찾아내 최적화를 할 수 있습니다.
(r, c)가 위치해 있는 사분면을 제외한 사분면을 굳이 방문하지 않고 해당 사분면들의 칸을 세는 것으로 순서를 찾아갈 수 있습니다.

아래 코드에서는 좌표계의 중앙 좌표 (x, y)와 (r, c)를 비교하여 사분면을 찾았습니다.
그리고 위치한 사분면을 따라서만 방문하며 그 외의 사분면에 있는 칸의 수를 세어줍니다.
최종적으로 마지막 깊이까지 도달했을 때 (r, c)에 방문한 것이며 그 때까지 세어준 칸의 수를 출력합니다.

사분면을 찾아내는 방법만 잘 구현하면 쉽게 해결할 수 있는 문제입니다!