Z_백준1074_재귀

 

-문제-

 

-문제 접근-

1. 배열 분할:
   • 전체 배열의 크기는 2^N × 2^N입니다.
   • 배열을 4등분하면 각 사분면의 크기는 2^(N-1) × 2^(N-1)가 됩니다.
2. 사분면 판별:
   • 현재 배열의 행의 중앙을 기준으로 r의 값이 작은 경우는 위쪽, 큰 경우는 아래쪽입니다.
   • 열의 중앙을 기준으로 c의 값이 작은 경우는 왼쪽, 큰 경우는 오른쪽입니다.
   • 이를 통해 (r, c)가 속하는 사분면은 아래와 같이 결정할 수 있습니다:
     • 0번 사분면 (왼쪽 위): r < half, c < half
     • 1번 사분면 (오른쪽 위): r < half, c ≥ half
     • 2번 사분면 (왼쪽 아래): r ≥ half, c < half
     • 3번 사분면 (오른쪽 아래): r ≥ half, c ≥ half
3. 방문 순서 오프셋 계산:
   • 각 사분면은 전체 방문 순서에서 연속적인 블록을 차지합니다.
   • 사분면 하나의 크기는 (2^(N-1)) × (2^(N-1))이고, 이 값은 각 사분면이 방문하는 칸의 개수입니다.
   • 예를 들어, 1번 사분면은 0번 사분면 다음부터 방문하므로, 그 시작 인덱스는 0번 사분면의 칸의 수와 동일합니다.
   • 따라서, (r, c)가 속하는 사분면의 번호에 해당하는 오프셋을 결과에 더해줍니다.
4. 좌표 조정:
   • (r, c)가 어떤 사분면에 속하는지 확인한 후, 그 사분면 내에서의 새로운 좌표는 원래 좌표에서 해당 사분면의 시작 좌표를 뺀 값이 됩니다.
   • 예를 들어, 오른쪽 위 사분면인 경우 c에서 2^(N-1)을 빼주어 해당 사분면 내의 좌표로 변환합니다.
5. 재귀적/반복적 해결:
   • 위의 과정을 N이 0이 될 때까지 재귀적으로 또는 반복문을 사용해 해결합니다.
   • N이 0이 되면, 더 이상 분할할 수 없으므로 결과를 반환합니다.

각 단계마다 (r, c)가 전체 Z 순서에서 몇 번째 위치에 있는지 누적해서 계산 가능합니다.

 

-코드-