[ 백준 1074 ] Z - Python

문제 보기

이 문제는 분할 정복, 재귀 호출 문제이다.

 

Z 형태로 배열을 탐색하기 위해서는 크기가 2 * 2가 될 때까지 4등분을 반복해야 하며 알고리즘 순서는 아래와 같다.

 

1. 주어진 배열을 4등분 한다. (분할 정복)

2. 1의 과정을 반복적으로 진행하면서 단위가 2*2일 때 탐색을 시작한다. (재귀 호출)

3. r, c를 탐색하면 출력하고 종료한다.

---

코드 (시간 초과)

def divide(size, start_row, start_col):
    global cnt
    if size == 2:
        if start_row == r and start_col == c:  # 왼쪽 위
            print(cnt)
            return
        cnt += 1
        if start_row == r and start_col + 1 == c:  # 오른쪽 위
            print(cnt)
            return
        cnt += 1
        if start_row + 1 == r and start_col + 1 == c:  # 왼쪽 아래
            print(cnt)
            return
        cnt += 1
        if start_row + 1 == r and start_col + 1 == c:  # 오른쪽 아래
            print(cnt)
            return
        cnt += 1
    else:
        divide(size // 2, start_row, start_col)
        divide(size // 2, start_row, start_col + size // 2)
        divide(size // 2, start_row + size // 2, start_col)
        divide(size // 2, start_row + size // 2, start_col + size // 2)


if __name__ == "__main__":

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

    cnt = 0
    divide(2 ** N, 0, 0)

 

코드

import sys


def divide(size, start_row, start_col):
    global cnt
    if size == 2:
        if start_row == r and start_col == c:  # 왼쪽 위
            print(cnt)
            sys.exit(0)
        if start_row == r and start_col + 1 == c:  # 오른쪽 위
            print(cnt + 1)
            sys.exit(0)
        if start_row + 1 == r and start_col == c:  # 왼쪽 아래
            print(cnt + 2)
            sys.exit(0)
        if start_row + 1 == r and start_col + 1 == c:  # 오른쪽 아래
            print(cnt + 3)
            sys.exit(0)
        cnt += 4
    else:
        if r <= start_row + size // 2 and c <= start_col + size // 2:
            divide(size // 2, start_row, start_col)
        else:
            cnt += (size // 2) ** 2

        if r <= start_row + size // 2 and c <= start_col + size // 2 * 2:
            divide(size // 2, start_row, start_col + size // 2)
        else:
            cnt += (size // 2) ** 2

        if r <= start_row + size // 2 * 2 and c <= start_col + size // 2:
            divide(size // 2, start_row + size // 2, start_col)
        else:
            cnt += (size // 2) ** 2

        if r <= start_row + size // 2 * 2 and c <= start_col + size // 2 * 2:
            divide(size // 2, start_row + size // 2, start_col + size // 2)
        else:
            cnt += (size // 2) ** 2


if __name__ == "__main__":

    N, r, c = map(int, sys.stdin.readline().split())

    cnt = 0
    divide(2 ** N, 0, 0)