[BOJ/Python] 1074_Z

문제 출처:https://www.acmicpc.net/problem/1074

1074번: Z

 

문제

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

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

다음 예는 2**2 × 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

---

풀이

 

우선 이 문제를 0부터 시작하여 해당 좌표까지 직접 탐색하게 되면, 예제 입출력 5,6의 경우처럼 매우 큰 범위까지 탐색을 하게 되므로 오랜 시간이 걸리게 된다.

 

이 문제는 결국 위 그림처럼 반복된 패턴의 연속이다.

첫 번째 8X8의 배열의 큰 틀을 살펴보면, 결국 왼쪽 위 -> 오른쪽 위 -> 왼쪽 아래 -> 오른쪽 아래 순으로 Z모양을 그리며 탐색하는 것을 알 수 있다.

그리고 그 배열을 4등분하여 4X4배열을 살펴본다면 결국 똑같은 방향으로 Z모양을 그리며 탐색을 하게 된다.

또 이 배열을 4등분하여 2X2배열을 만들어 살펴보더라도 같은 패턴으로 탐색함을 알 수 있다.

즉, 우리는 주어진 행과 열이 배열을 4등분 하였을 때, 어디에 위치하는 지를 이용하여 이 문제를 해결할 수 있다.

여기서 하늘색 부분을 몇 번째로 방문했는지 구한다고 생각해 보자.

• 8X8배열을 4등분을 한다.
• 여기서 나누어진 영역 중, 왼쪽 아래의 영역에 존재하게 된다.
• 왼쪽 위 -> 오른쪽 위 -> 왼쪽 아래 -> 오른쪽 아래 순으로 탐색하므로, 왼쪽 위와 오른쪽 위를 탐색한 이후에 녹색 테두리 부분을 탐색함을 이용한다.
• 그러면 왼쪽 위 16개의 좌표, 오른쪽 위 16개의 좌표를 탐색한 이후에, 녹색 테두리 영역의 좌표를 탐색함을 알 수 있다.
• 이를 이용하면, 우리가 구해야 하는 답이 32 + (녹색 테두리 내부에서의 하늘색 영역의 방문 순서) 임을 알 수 있고, 왼쪽 위와 오른쪽 위의 좌표들을 차례로 계산하는 불필요한 과정을 생략할 수 있다.
• 이제 4X4 녹색 테두리 내부에 영역을 살펴보자

• 여기서도 마찬가지로 4X4배열을 4 등분한다.
• 4 등분하였을 때, 녹색 테두리 내부에 하늘색 영역이 존재하게 된다.
• 마찬가지로 왼쪽 위 -> 오른쪽 위 -> 녹색 테두리 내부 영역 -> 오른쪽 아래 순으로 탐색한다.
• 그러면 4X4 배열 내부에서의 탐색 순서는 4개의 좌표 + 4개의 좌표 + (녹색 테두리 내부에서 하늘색의 영역의 방문 순서) 임을 알 수 있다.
• 이제 여기서의 녹색 테두리 내부 ( 2X2 배열)를 살펴보자

 

 

• 4등분을 하였을 때, 오른쪽 위에 존재함을 알 수 있다.
• 문제에서 0부터 탐색을 시작하였으므로, 이 경우 1이 된다.
• 이제 구한 값들을 거꾸로 다시 살펴보면 다음과 같다.
• 2X2에서 구한 값 : 1
• 4X4에서 구한 값 : 8+ (2X2 내부에서의 방문 순서)
• 8X8에서 구한 값 : 32+ (4X4 내부에서의 방문 순서)
• 이제 구한 값들을 종합하게 되면, 32 + 8 + 1 = 41이 된다.

 

 

코드를 살펴보면 다음과 같다.

 

import sys
 
def find(n,r,c):
    area = 2**(n-1) * 2**(n-1)
    if n==-1:
        return 0
 
    if r<2**(n-1):
        if c<2**(n-1):
            return find(n-1,r,c)
        else:
            return area + find(n-1,r,c%(2**(n-1)))
    
    else:
        if c<2**(n-1):
            return area*2 + find(n-1,r%(2**(n-1)),c)
        else:
            return area*3 + find(n-1,r%(2**(n-1)),c%(2**(n-1)))
 
 
n,r,c = map(int,sys.stdin.readline().split())
print(find(n,r,c))

 

• 우선 재귀를 이용하여, 해당 좌표가 4등분을 하였을 때 어디에 위치하는 지를 탐색하였다.
• 만약 오른쪽 위 부분(r <2**(n-1) and c>=2**(n-1))이라면, 왼쪽 위의 영역을 모두 탐색한 이후에 탐색하므로, 왼쪽 위의 영역인 area만큼 더해주고 재귀를 진행하였다.
• 왼쪽 아래의 경우는 왼쪽 위와 오른쪽 위를 더해줘야 하므로 2*area를 더해주었고, 오른쪽 아래는 3*area를 더해주었다.
• 재귀에 경우, 4등분을 하여 그 작은 부분으로 들어가서 다시 탐색을 시작한다.
• 여기서 4등분을 하게 되면 영역 또한 4등분이 되고, 그러면 좌표의 값도 수정을 해 주어야 한다.
• 왼쪽 위 영역 내부의 좌표는 4등분을 하더라도 좌표가 그 범위 내부이기 때문에 상관이 없다.
• 하지만, 다른 영역들의 경우 좌표가 범위를 초과하는 경우 2**(n-1)로 나눈 나머지값을 좌표로 설정한다.
• 그리고 이런 식으로 계속 영역을 4 등분하여 탐색을 하다가 n이 -1이 되면, 0을 return 한다. (0부터 탐색을 시작하기 때문이다.)