[ 백준 / 파이썬 ] 실버 1 - 1074. Z

난이도

문제

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

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

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

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

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

입력

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

##출력

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

#제한

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

예제 입력

입력	출력
2 3 1	11
3 7 7	63
1 0 0	0
4 7 7	63
10 511 511	262143
10 512 512	786432

풀이

가장 처음 풀이는 2차원 배열을 생성하여 Z 모양으로 수를 채워 나갔다.
하지만 이렇게 풀면 $2 ^{15}$ 이나 되는 크기의 배열을 만들 수 없어 메모리 초과가 발생한다.

그래서 수를 채워나가는 공식과 동일한 방법으로 몇 사분면에 존재하는 지 파악하고, 하나씩 값을 채우는게 아닌 해당 사분면 만큼 값을 더하는 방법으로 풀이한다.

큰 사각형을 4분면으로 쪼개면서 내가 원하는 좌표 위치에 해당하는 값을 찾아간다.

이 때 사각형의 크기가 $2 \times 2$ 가 되면, 그 때 부턴 하나씩 움직이면서 찾는다.

코드

cnt = -1


def solution(N, r, c):
    global cnt
    draw(N, 0, 0, r, c)


def draw(N, sx, sy, r, c):
    global cnt
    now = 2 ** (N-1)
    if N == 1:
        for i in range(2):
            for j in range(2):
                cnt += 1
                if i == r and j == c:
                    print(cnt)
                    quit()
        return

    if 0 <= c < 2 ** (N - 1):
        if 0 <= r < 2 ** (N - 1):
            # 2사분면
            cnt += 0
            draw(N - 1, 0, 0, r, c)

        else:
            # 3사분면
            cnt += now**2 * 2
            draw(N - 1, 0, 2 ** (N - 1), r-now, c)

    else:
        if 0 <= r < 2 ** (N - 1):
            # 1사분면
            cnt += now**2
            draw(N - 1, 2 ** (N - 1), 0, r, c-now)

        else:
            # 4사분면
            cnt += now**2 * 3
            draw(N - 1, 2 ** (N - 1), 2 ** (N - 1), r-now, c-now)



N, r, c = map(int, input().split())
solution(N, r, c)