백준 1074 파이썬 - Z

머엉... 재귀함수에 아직 익숙하지 않아서 어렵다 ! 

이 문제를 읽으면 

재귀함수가 딱 떠오른다

0-1-2-3 이렇게 4칸을 Z 모양으로 탐색한다

그런데 분명 재귀함수를 써야할 것 같은데.. 어디서 쓰면 좋을지 이해하는게 관건이다

처음에는 4칸씩 확장해 나가다가 c행 r열 칸을 찾으면??? 될까 라는 생각을 함

근데 큰 정사각형 덩어리에서 4분의 1 (즉 2*(n-1) * 2*(n-1))로 줄어든다는 것으로 접근하는게 쉽다

그러니까 큰 정사각형을 4칸으로 자르고

또 잘라진 4칸을 각각 잘라진 4분의 1 정사각형에서 4칸으로 자르고... 

즉 !! N의 값이 N/2로 연산 할때마다 줄어든다!! 

그리고 시작점을 (x,y)==(0,0)라고 생각한다 

# 1074 py

N, r, c = map(int, input().split()) # 주어지는 수 입력받기 !! 

count = 0 # 결과값 (칸의 숫자) 초기화

def solve(N, x, y): # 재귀함수
    global count
    if x == r and y == c: # 현재 (x,y)의 좌표값이 우리가 찾는 r,c와 같으면 
        print(int(count)) # count 출력하고 함수 종료 !!
        exit(0)

    if N == 1: # N==1인 경우 우리가 4개씩 나눈 사각형이 1칸짜리가 된다는 것이다.
        count += 1 # 이 경우 한칸씩 이동하면서 count 값을 하나씩 더해준다 !! 
        return

    if not (x <= r < x + N and y <= c < y+N): 
        count += N*N
        return

    solve(N/2, x,y)
    solve(N/2,x,y+N/2)
    solve(N/2,x+N/2,y)
    solve(N/2,x+N/2,y+N/2)

solve(2**N, 0, 0)

 

코드를 조금 더 살펴보자면, if 문에서

    if not (x <= r < x + N and y <= c < y+N):
        count += N*N
        return

현재 좌표의 위치인 (x, y) 가 우리가 탐색하고자 하는 범위 내에 없다면 ???? 그래서 if not (x좌표의 조건 and y좌표의 조건) 

그 범위에는 한칸짜리 정사각형 (count 개수의 단위가 된다)이 N * N 개 있으니까 전체를 더해주고 그 다음 탐색으로 넘어가~~ 

이말을 그림으로 표현하면 다음과 같다 

저 파란 정사각형 내부에 있지 않으면 

N*N 싸악 count 변수에 더해주고 ! 재귀함수는 2사분면, 3사분면, 4사분면을 탐색한다 

어떻게 ??? 이렇게 !! 되게 재귀함수 문제에서 자주보는 호출방식인것 같다 

    solve(N/2, x,y)
    solve(N/2,x,y+N/2)
    solve(N/2,x+N/2,y)
    solve(N/2,x+N/2,y+N/2)

순회가 필요한 구간을 나누어서 재귀적으로 호출해주는것이다 4분의 1씩 사각사각..

하나씩 분석해보니까 유별나게 어려운 문제는 아니었다 !! 재귀함수는 코드가 예뻐서(?) 좋다능

골드를 향해 화이팅!!