[python] 백준 온라인 알고리즘 1074번 Z, dfs 풀이

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

1074번: Z

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

def Z(size, x,y):
    if size == 1:
        return 0
    size = size // 2
    for i in range(2):
        for j in range(2):
            if x < size * (i+1) and y < size *(j+1):
                return (2*i + j)*(size**2) + Z(size, x-i*size, y-j*size)

print( Z( 2**N, r, c ) )

 

Z

dfs를 사용하여 재귀적으로 풀었으며,

매개변수를 입력 받을때, 사각형의 한변의 크기(size)를 받고,

dfs함수 내부적으로 size= size // 2를 사용하여 4등분한 사각형 한변의 크기를 이용하였다.

if x < size * (i+1) and y < size *(j+1):

위 조건의 의미는 작은 사각형 한변을 기준으로 매개변수로 입력받은 x, y가 저 범위 안에 들어 가는지를 알아보는 것이다.

한변은 크기는 0이 될 수 없으므로 index에 1씩 더해주는 것이다.

return (2*i + j)*(size**2) + Z(size,x-i*size,y-j*size)

위 코드 블럭에서 앞부분을 설명하자면,

(2*i + j)*(size**2)

i	j	number
0	0	0
0	1	1
1	0	2
1	1	3

2*i +j를 통해 사각형 index 0, 1, 2, 3을 Z 모양으로 돌기위해 붙인것이고,

만약 작은 사각형 2번이 선택 되었다고 치면, 

그 앞전 지나간 사각형 개수를 선택된 index에 곱해주는 것이다.

Z(size,x-i*size,y-j*size)

재귀 부분 함수는 2로 나누어진 size를 매개변수로 주고,

원래 받았던, x, y를 작은 사각형 한변의 크기만큼 i,j에 곱하여 빼주게 되면 

r,c = 3,1

재귀적으로 2번 사각형에 들어가게되고,

2번 사각형 안에서 또 4등분되어 우리가 목표로하는 (1,1) 인덱스가 dfs함수로 들어가게 된다.

stack에 쌓여있던, Z()함수들이 호출되고 

답  11을 반환하게 된다.