[python] 백준 > 분할정복, 재귀 > Z(1074)

[문제]

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

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

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

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

입력

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

출력

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

제한

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

www.acmicpc.net/problem/1074

1074번: Z

[풀이]

import sys
input = sys.stdin.readline

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

# n: 변의 길이,x: 현재 위치의 x축 값, y:현재 위치의 y축 값
result = 0
def N(n, x, y):
    global result

    if x==r and y==c:
        print(int(result))
        exit(0)

    if n == 1:
        result += 1
        return

    if not(x<=r<x+n and y<=c<y+n):
        result += n*n
        return

    # 1사분면
    N(n/2, x, y)
    # 2사분면
    N(n/2, x, y+n/2)
    # 3사분면
    N(n/2, x+n/2, y)
    # 4사분면
    N(n/2, x+n/2, y+n/2)

N(2**n, 0, 0)

• 재귀함수에대해 완전히 이해할 수 있는 문제였다.
• 4개씩 쪼개서 (r,c)가 있는 위치가 아니라면 나머지 3분면에 있는 갯수를 다 더해준다.
• 그리고 (r,c)가 존재하는 분면을 다시 4등분해서 똑같이 탐색한다.
• 총 4개의 정사각형만 남았을 때, 정사각형 한개씩 탐색을 해서 (r,c)가 아니라면 1만 더해주고 리턴한다.
• (r,c)가 있는 곳까지 왔을 때, 지금까지 더해준 result를 출력해준다.