[🥈1 / 백준 1074 / 파이썬] Z

 

1074번: Z

 

문제

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

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

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

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

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2^N

 

예제 입력 1 2 3 1	예제 출력 1 11
예제 입력 2 3 7 7	예제 출력 2 63
예제 입력 3 1 0 0	예제 출력 3 0
예제 입력 4 4 7 7	예제 출력 4 63
예제 입력 5 10 511 511	예제 출력 5 262143
예제 입력 6 10 512 512	예제 출력 6 786432

 

풀이

 

배열의 최대 크기가 2^30 로, 전체 탐색을 사용한다면 최대 약 10억번의 연산이 필요하다.

따라서 필요한 곳만 탐색하고 나머지는 빠르게 넘기기 위해 분할 탐색 알고리즘을 사용한다.

 

분할 탐색을 시행할 때 중요한 점은 재귀로 모든 부분을 분할하여 탐색하면 안 된다는 것이다.

그렇게 한다면 전체 탐색과 순서만 달라질 뿐이지, 결과적으로는 시간복잡도의 개선이 없다.

 

 

위 그림과 예제 1을 이용하여 문제를 풀어보겠다.

 

분할 탐색은 DP와 반대로 Top-Down 방식이다.

따라서 전체부터 시작하여 작은 부분으로 내려간다.

 

한 변의 길이는 2^2 이므로 4, 시작 지점인 (x,y)는  (0,0) 으로 진행한다.

이제 시작 지점에서 한 변의 길이를 더한 범위 내에 r과 c가 포함된다면 분할 탐색을 한다.

만약 포함하지 않는다면 변의 제곱을 반환하여 칸 수를 한 번에 계산한다.

 

 

범위 내에 (3,1)이 포함된다. 분할 탐색을 진행한다.

 

 

Z 방향대로 분할 탐색을 한다.

빨간색 테두리를 친 부분에 (3,1) 부분이 없으므로 한 변의 길이인 2의 제곱을 반환하여 칸 수를 한 번에 return한다.

그리고 다음 부분으로 넘어간다.

 

 

마찬가지로 범위 내에 (3,1)이 없으므로 칸 수를 return하고 다음으로 넘어간다.

 

 

마침내 (3,1) 좌표를 포함하게 되었다.

이미 2*2로 분할의 최소 범위이기 때문에 분할 탐색 대신 실제로 좌표를 세어주면 된다.

(x,y), (x,y+1), (x+1,y), (x+1,y+1) 순서로 진행하여 순서에 맞게 칸 수를 더해준 뒤 출력한다.

 

import sys

def dc(x,y,n):
    global cnt
    if x>r or x+n <= r or y>c or y+n <= c:
        cnt += n**2
        return 
    
    if n > 2:
        n//=2
        dc(x,y,n)
        dc(x,y+n,n)
        dc(x+n,y,n)
        dc(x+n,y+n,n)
    else:
        if x==r and y==c:
            print(cnt)
        elif x==r and y+1==c:
            print(cnt+1)
        elif x+1==r and y==c:
            print(cnt+2)
        else:
            print(cnt+3)
        sys.exit()
        
n,r,c = map(int,input().split())
cnt = 0
dc(0,0,2**n)