백준 1074번 Z [Python]

[Silver I] Z - 1074

문제 링크

성능 요약

메모리: 31120 KB, 시간: 44 ms

분류

분할 정복, 재귀

제출 일자

2024년 4월 2일 15:51:35

문제 설명

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

풀이

Z모양으로 방문하며 탐색을 해야 하는데, N의 크기가 커지면 커질 수록 분할해야하는 문제도 점점 많아진다. 좌표(r,c)의 값을 구하려면 4개의 정사각형으로 나눠가며 해당하는 정사각형에 진입해야한다.

아래 코드에서는 일반적인 2차원 함수 그래프에서 적용되는 사분면 위치를 적용했다. 즉, Z탐색 순서는 2 -> 1 -> 3 -> 4 가 된다.

전체 코드

import sys
input = sys.stdin.readline

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

while N != 0:
    N -= 1

    # 1사분면
    if r < 2**N and c >= 2**N:

        # N의 크기에 따른 1사분면 해당 값 계산
        res += (2**N) * (2**N) * 1
        c -= (2**N) # Z시작점 지정(2사분면)

    # 2사분면
    elif r < 2**N and c < 2**N:

        # N의 크기에 따른 2사분면 해당 값 계산
        res += (2**N) * (2**N) * 0
        # 이미 시작점이 2사분면이므로 r,c좌표값 수정 X

    # 3사분면
    elif r >= 2**N and c < 2**N :

        # N의 크기에 따른 3사분면 해당 값 계산
        res += (2**N) * (2**N) * 2
        r -= (2**N) # Z시작점 지정(2사분면)

    # 4사분면
    else:

        # N의 크기에 따른 3사분면 해당 값 계산
        res += (2**N) * (2**N) * 3

        # Z시작점 지정(2사분면)
        r -= 2**N
        c -= 2**N

print(res)