[Python 3] BOJ - 1074 "Z"

 # 문제 링크 : https://www.acmicpc.net/problem/1074

1074번: Z

 

 # 풀이 :

개인적으로 이 문제의 핵심은 항상 4등분이 된다는 점, 즉 이를 사분면으로 처리하는 것이라고 생각한다. 문제에서 주어지는 2차원 배열의 크기가 2의 거듭제곱 꼴이고 정방 행렬이므로 시작 행과 끝 행을 반으로 나누고, 시작 열과 끝 열을 반으로 나누게 되면 항상 4개의 사각형으로 분할이 가능하다.

 문제에서 Z의 모양대로 방문하는 순서를 정했는데, 항상 4개의 사각형으로 분할이 가능하므로 분할 후 1,2,3,4 분면으로 이동해주면 된다.

<그림 1. n = 2일 때 첫번째 분할>

 위 그림1에서 각 4분면이 사이즈가 4짜리인 사각형으로 분할된 모습이다. 그런데, 각 사분면의 처음 시작하는 부분, (0,0) / (0,2) / (2,0) / (2,2) 일 때 4의 거듭제곱 꼴이다. 각각 n사분면은 4 * (n - 1) 부터 시작됨을 알 수 있다.

<그림 2. n = 2일 때 두번째 분할>

 위 그림 2에서도 각 n사분면은 (분할된 사각형의 사이즈) * (n - 1)로 시작함을 알 수 있다. 따라서 가장 처음에 시작하는 0행 0열의 방문 횟수를 0으로 놓고 분할 정복을 수행하면 정답을 올바르게 구할 수 있다.

 

 # 코드

import sys

# div : 분할 정복하는 함수
def div(row_start, row_end, col_start, col_end, num):
    # 정답을 찾은 경우
    if r == row_start and c == col_start:
        print(num)
        return
    # row_mid : 사분면을 나누기 위한 행의 경계값
    # col_mid : 사분면을 나누기 위한 열의 경계값
    row_mid = (row_start + row_end) // 2
    col_mid = (col_start + col_end) // 2

    # n : 분할된 사각형의 사이즈
    n = (row_mid - row_start) * (col_mid - col_start)

    # 각 사분면 마다 규칙성 적용
    if row_start <= r < row_mid and col_start <= c < col_mid:
        div(row_start, row_mid, col_start, col_mid, num)
    elif row_start <= r < row_mid and col_mid <= c < col_end:
        div(row_start, row_mid, col_mid, col_end, num + n)
    elif row_mid <= r < row_end and col_start <= c < col_mid:
        div(row_mid, row_end, col_start, col_mid, num + 2 * n)
    elif row_mid <= r < row_end and col_mid <= c < col_end:
        div(row_mid, row_end, col_mid, col_end, num + 3 * n)

# 입력부
n,r,c = map(int, sys.stdin.readline().split())

# 정답 출력
div(0, 2 ** n, 0, 2 ** n, 0)