[백준] 1074 Z (Python 파이썬)

문제 설명

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

1074번: Z

현재 주어진 2차원 배열을 4사분면으로 쪼갠 후, 각 사분면에 대해 다시 또 4사분면으로 쪼개면서

각 사분면이 1칸이 될 때 까지 계속 쪼갠 후 방문 순서를 정하는 문제이다.

결국, 내가 입력한 r행 c열을 몇 번째로 방문하는지 구하는 문제이다.

---

풀이 과정

여기서 주의깊게 봐야할 점은 항상 왼쪽위(1사분면) -> 오른쪽위(2사분면) -> 왼쪽아래(3사분면) -> 오른쪽아래(4사분면) 의 방향을 지키면서 각 칸을 방문한다는 것이다. (Z모양)

 

처음 8x8 배열이 있으면,

처음에는 (0, 0) ~ (3, 3) 까지인 1사분면을 방문할 것이고,

또 그 1사분면을 4 x 4 배열 하나로 본 후, 4사분면으로 쪼개 1, 2, 3, 4 사분면으로 나눠 방문 순서를 정할 것이다.

 

이 때, 문제에서 N은 15이하의 수이므로

2 ^ 15 x 2 ^ 15칸을 모두 방문하게 되면 시간초과가 나게 된다.

 

따라서, 내가 찾는 칸이 현재 범위에 없다면 N * N 만큼 칸을 스킵하도록 해야 한다.

 

예를 들어, 내가 찾는 칸이 3사분면에 있다면 1사분면과 2사분면은 모두 검사할 필요 없이 단순히 스킵하면 된다.

이 부분이 if not (x <= r < x + N and y <= c < y + N) 부분이다.

n, r, c = map(int, input().split())
num = -1


def recursive(x, y, N):
    global num

    if N == 2:
        for i in range(x, x + N):
            for j in range(y, y + N):
                num += 1
                if i == r and j == c:
                    print(num)
                    exit(0)
        return

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

    for i in range(x, x + N, N // 2):
        for j in range(y, y + N, N // 2):
            recursive(i, j, N // 2)


recursive(0, 0, 2 ** n)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !