BOJ-1074 Z

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

문제 소개

크기가 $2 ^ N * 2 ^ N$ 인 2차원 배열을 Z자 모양으로 탐색하는 문제이다. N > 1인 경우, 배열을 크기가 $2 ^ {N - 1} * 2 ^ {N - 1}$ 로 4등분 한 후에 재귀적으로 순서대로 방문한다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 구한다.

문제 풀이

r행 c열의 원소가 현재 배열의 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 중 어느 곳에 위치하는지 판단하는 것을 반복적으로 수행하여 최종 위치를 알아내도록 풀이하였다.

코드에서 쓰인 변수의 의미는 아래와 같다.

• size : 현재 배열의 행 또는 열의 길이
• start : 현재 배열의 시작 값
• end : 현재 배열의 끝 값

반복문을 통해 size가 1이 될 때까지 4등분된 배열 중 어느 위치에 목표값이 있느냐에 따라 r, c, start, end를 갱신한다.

코드

n, r, c = map(int, input().split())

size = 2 ** n
start, end = 0, size ** 2 - 1

while size > 1:
    # 위쪽에 위치
    if 0 <= r < size // 2:
        # 왼쪽 위에 위치
        if 0 <= c < size // 2:
            end = end - size ** 2 // 4 * 3
        # 오른쪽 위에 위치
        else:
            c -= size // 2
            start = start + size ** 2 // 4
            end = end - size ** 2 // 4 * 2
    # 아래에 위치
    else:
        # 왼쪽 아래에 위치
        if 0 <= c < size // 2:
            r -= size // 2
            start = start + size ** 2 // 4 * 2
            end = end - size ** 2 // 4
        # 오른쪽 아래에 위치
        else:
            r -= size // 2
            c -= size // 2
            start = end - size ** 2 // 4 + 1
    size //= 2
    # print(f"start : {start}, end : {end}, size : {size}")
    # print(f"r : {r}, c : {c}")

print(start)

아래쪽의 주석 처리된 두 줄을 통해 매 반복의 탐색 과정을 살펴볼 수 있다.