BOJ 1074 Z

Z

문제

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

만약, 2차원 배열의 크기가 2^N _ 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면,
배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.
다음 예는 2^2 _ 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고,
r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

2 3 1

3 7 7

예제 출력

11

63

풀이

4중 분할 정복을 활용하는 문제다.
행렬의 크기가 주어졌을 때 주어진 좌표 (r, c)가 Z 알고리즘을
사용했을 때 몇 번째로 방문하게 되는지 확인하는 문제다.
분할 정복 문제인 만큼 재귀를 사용해서 구현할 수도 있지만
실행 시간의 최적화를 위해서 반복을 사용해서 구현해 보도록 하겠다.

변수 설명

구현에 앞서 구현에 사용되는 변수 몇 가지를 설명하겠다.

• size : 2차원 행렬의 크기
• reult : 탐색 순서 결과
• r : 행렬의 행 좌표
• c : 행렬의 열 좌표
• temp_r : 사이즈가 변경된 행렬의 행을 계산할 때 사용
• temp_c : 사이즈가 변경된 행렬의 열을 계산할 때 사용

예제 분석

예제 1번의 흐름(?)을 그림으로 그려본 것이다.
검은 원인 (3, 1)은 처음에 입력으로 받은 r, c에 해당하는 것이고
파란 원인 8과 11은 result 값이다.
빨간 선은 4 X 4 행렬의 Z 알고리즘 흐름이다.

변수들의 값은 다음과 같이 변한다.

size = size // 2
temp_r = r // size
temp_c = c // size

result += ((temp_r * 2) + temp_c) * pow(size, 2)
r = r - (temp_r * size)
c = c - (temp_c * size)

• size = 4 // 2 = 2
• temp_r = 3 // 2 = 1
• temp_c = 1 // 2 = 0
• result += ((1 * 2) + 0) * pow(2, 2) = 2 * 4 = 0 + 8
• r = 3 - (1 * 2) = 1
• c = 1 - (0 * 2) = 1

result의 값은 4 X 4 행렬이 2 X 2 행렬 4개로 분할되면서 생긴
(0, 0)의 탐색 순서에 해당한다.

(2, 0)에 해당하는 8이 result값에 대입되었다.
또한 2 X 2 크기로 변한 행렬에서 찾으려는 값은 새로운 (r, c)에 존재한다.
한 문장으로 정리하자면 2 X 2로 분할된 새로운 행렬의 (1, 1)에 존재하게 되는 것이다.
4분할 된 행렬의 tempr = 1, tempc = 0은 3사분면을 가리킨다.
(0, 0) = 1사분면, (0, 1) = 2사분면, (1, 0) = 3사분면, (1, 1) = 4사분면이 된다.
4분할된 행렬의 (2 * tempr) + tempc번째 행렬이 되는 것이다.
현재 result의 값에 (x사분면) X (행렬의 크기의 제곱)을 더 해주면
현재 사분면의 (0, 0)의 순서 값을 얻을 수 있다.
해당 예제는 ((2 * 1) + 0) * pow(2, 2)로 8의 값을 얻을 수 있다.

다음과 같은 테이블로 (1, 1)의 데이터는 (2 * 1) + 1번째 데이터임을 알 수 있다.
해당 식을 일반화하게 되면 (2 * r) + c의 값을 현재 result변수에 더해준다면
몇 번째 순서로 해당 행렬을 방문하게 되는지 확인할 수 있다.
이것에서 알 수있듯이 반복(재귀)의 탈출 조건은 r과 c가 2보다 작을 경우가 된다.
다음과 같은 코드로 표현할 수 있겠다.

if r < 2 and c < 2:
    result += 2 * r + c
    break

다음과 같은 방법으로 행렬의 크기를 절반으로 나눠주면서 해당 행렬의 (0, 0)에
해당하는 값을 계산해 result에 갱신한 후 r과 c 둘다 2보다 작은 경우
즉 (0, 0), (0, 1), (1, 0), (1, 1) 같이 2 X 2행렬의 크기가 되면 반복을 탈출하게 된다.

코드 구현부

import sys

N, r, c = map(int , sys.stdin.readline().split())

size = pow(2, N)
result = 0

while True:
    if r < 2 and c < 2:
        result += (r * 2 + c)
        break

    size = size // 2
    temp_r = r // size
    temp_c = c // size

    result += ((temp_r * 2) + temp_c) * pow(size, 2)
    r = r - (temp_r * size)
    c = c - (temp_c * size)

print(result)

결과

재귀를 사용하지 않고 반복문을 사용해서 풀었다.
4분할 문제답게 사분면을 사용하여 접근하였으며, (2 * r) + c로 일반화된 공식을
사분면, 좌표 두개 다 사용해 접근할 수 있었다.
설명 부분에 있어 모자른 부분이 조금 있는 것 같아 추후에 수정을 좀 해야할 것 같다.

✅ 코드는 [여기]에서 확인할 수 있다.