[BOJ 1074] Z

문제 링크 : https://www.acmicpc.net/problem/1074

본문

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2² × 2² 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

제한

시간 제한	메모리 제한
0.5sec (추가 시간 없음)	512MB

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2^N

---

풀이

진짜 간단한 문제다. 내가 구현하려는 목적이 무엇인지 확인하고 그대로 구현해내도록 노력해보자.

문제의 내용 자체가 재귀함수를 써달라고 이야기하고 있다. $2^N \times 2^N$ 크기의 배열을 4등분하여 생각하도록만 구현하면 나머지는 프로그램이 알아서 계산해줄 것이다. 칸의 개수를 세는 방법만 잘 정해주면 풀리는 문제.

일단 $N$이 주어졌다면, 배열은 총 $2^{2N} = 4^N$칸이 존재한다. 그 중 찾으려는 칸이 어떤 범위에 존재하는지 확인하면 된다. 총 4가지 경우가 있다.

• $[0, \frac{1}{4}]$ 범위 : 왼쪽 상단
• $[\frac{1}{4}, \frac{1}{2}]$ 범위 : 오른쪽 상단
• $[\frac{1}{2}, \frac{3}{4}]$ 범위 : 왼쪽 하단
• $[\frac{3}{4}, 1]$ 범위 : 오른쪽 하단

분면 순서대로 움직이기 때문에 탐색된 칸의 개수를 셀 때 편해진다. 만약 내가 찾으려는 칸이 왼쪽 하단에 소속된 칸이라면 왼쪽 상단과 오른쪽 상단의 칸들은 모두 탐색한 뒤에 진행될 것이므로, 2개의 분면에 존재하는 칸보다는 늦게 탐색될 것이고, 방문 순번은 최소 2개 분면의 칸의 수를 더한 값보다는 클 것이다. 이 방식으로 가장 큰 배열에서부터 탐색 범위를 줄여나가는 과정을 진행하면 답을 얻을 수 있다.

각 분면에 속해있는지 결정하는 방법은 $r$과 $c$가 특정 범위에 속해있는지 확인하면 된다. 탐색해야하는 칸의 순번이 총 칸의 개수 $4^N$의 절반보다 크다면 아랫쪽, 아니라면 윗쪽일 것이다. 이 조건으로 $r$행이 어느 분면에 속할지 유추할 수 있다. 마찬가지로 $c$열의 위치도 유추해낼 수 있다. 이 과정을 끝까지 반복하여 $N=1$일 때까지 문제를 쪼개 생각하고, 정확한 $r$행 $c$열의 순번을 계산해내면 된다.

소스코드

Github Link : Source Code

참고 알고리즘 : 분할정복 알고리즘