백준 1074: Z - 분할정복(파이썬)

Z 성공2

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열을 몇 번째로 방문했는지 출력한다.

제한

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

 

 

내 코드

import sys

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

answer=0
while n!=0:

    n-=1
    size=2**n

    # 좌표가 1사분면에 속할 때
    if r<size and c<size:
        pass #추가적인 조정 필요 X

    # 좌표가 2사분면에 속할 때
    elif r<size and c>=size:
        answer+=size*size #1사분면만큼 pass
        c-=size
        
    # 좌표가 3사분면에 속할 때
    elif r>=size and c<size:
        answer+=size*size*2 #1, 2사분면만큼 pass
        r-=size

    # 좌표가 4사분면에 속할 때
    else:
        answer+=size*size*3 #1, 2, 3사분면만큼 pass
        r-=size
        c-=size
    

print(answer)

 

풀이 및 접근)

- 처음에 (x,y) 좌표를 통해 일반화를 하려했는데 일반화가 되지 않았다. 이 문제는 분할정복을 통해 푸는 문제이다.

- 그림을 크게 봤을 때 Z모양 순서대로 탐색을 한다. 이것을 전체 -> 1/4크기 -> 1/4크기 -> ... 의 모든 과정에서 적용시키면 된다.

- 특정 좌표가 어느 사분면에 속해있는지를 계속 탐색해 나가면서, 최종 탐색 순서를 찾아야 한다. 특정 사분면마다 더해주어야 하는 값들이 필요하다

- 특정 사분면에 속했을 때 각각의 필요한 값을 answer에 누적한 후, (r,c)의 위치를 1사분면으로 조정한다. 그 후  크기를 1/4로 줄여나가면서 이 과정을 계속 반복한다.

- 그렇게 되면 최종적으로 2*2 사이즈일 때 최종 위치에 대한 정보를 더해 정답을 얻어낼 수 있다.