[lv3] 1074. Z(Python 파이썬 풀이)

출처

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

1074번: Z

문제

한수는 크기가 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

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

해석

이 문제는 재귀를 이용하면 쉽게 풀 수가 있다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 4분열 시킨다. 그리고 원하는 좌표 지점으로 근접하도록 분열한 곳 중에서 필요한 위치로 이동시킨다. 필요 없는 위치들은 result값에 추가시킨다. 분열을 계속 하다보면 더이상 분열할 수 없는 곳에 도달한다. 즉 m의 값이 1일 때, 그때는 4등분을 시킨 곳을 하나하나 보면서 우리가 찾는 r,c이랑 맞는지 확인하면서 result값에 1씩 추가하여 답을 구하면 된다.

소스 코드

import sys
sys.stdin = open("1074in.txt",'r')
 
def zmaze(m,y,x):
    global result
    if y==a and x == b:
        print(result)
        exit(0)
 
    if m==1:
        result += 1
        return
    
    if not ( y <= a < y + m and x <= b < x+m):
        result += m*m
        return
    zmaze(m//2, y, x )
    zmaze(m//2, y, x + m//2 )
    zmaze(m//2, y + m//2, x )
    zmaze(m//2, y + m//2, x+ m/2 )
 
 
result = 0
n,a,b = map(int,sys.stdin.readline().split())
zmaze(2**n,0,0)