[Python/파이썬] 백준 1074번 Z

1074번: Z

 

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

코드

처음에 푼 코드 => 시간 초과!

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

cnt = 0
def visit(length, row, col):
    global cnt
    if row == r and col == c:
        print(cnt)
        exit()
    if length == 1:
        cnt += 1
        return
    visit(length//2, row, col)
    visit(length//2, row, col+length//2)
    visit(length//2, row+length//2, col)
    visit(length//2, row+length//2, col+length//2)
    return

visit(2**n, 0, 0)

• 우리가 찾는 위치가 나오면 바로 몇번째로 방문했는지 출력하고 프로그램을 종료하게 해서 시간 초과를 해결해보려 했지만 배열의 크기가 (2 ^ N) * (2 ^ N) (1 ≤ N ≤ 15)이라서 시간 초과가 났다...

 

정답 풀이

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

ans = 0

while n != 0:
    n -= 1
    # 왼쪽 위
    if r < 2**n and c < 2**n:
        ans += (2**n) * (2**n) * 0
    # 오른쪽 위
    elif r < 2**n and c >= 2**n:
        ans += (2**n) * (2**n) * 1
        c -= (2**n)
    # 왼쪽 아래
    elif r >= 2**n and c < 2**n:
        ans += (2**n) * (2**n) * 2
        r -= (2**n)
    # 오른쪽 아래
    else:
        ans += (2**n) * (2**n) * 3
        r -= (2**n)
        c -= (2**n)
        
print(ans)

이 코드의 시간 복잡도는 O(n)으로 위의 코드와는 비교가 안되게 짧다.

코드도 복잡하지 않다. r, c가 있는 정사각형으로 점점 정사각형 크기를 줄여가며 찾는다고 생각하면 된다.