1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 전형적인 재귀, 분할 정복으로 해결할 수 있는 문제였습니다. 입력받은 좌표가 전체 영역에서 어떤 사분면에 위치하는지 파악 후 이들을 분할한 뒤 또 어떤 사분면에 해당하는지 위치를 알아가면 해결할 수 있는 문제였습니다.
그림으로 설명하겠습니다.
n이 3인 경우를 예로 들겠습니다.
4행 6열즉 52가 몇 번째로 탐색이 되는지 판단해봅시다. (이미 52라 나와있긴 합니다만...)
우선 크게 4개의 사분면으로 쪼개면 해당 좌표는 4 사분면에 위치합니다. 그 후 쪼개면 다음 그림과 같습니다.
이렇게 분할하면 이번에는 2 사분면에 위치하는 것을 알 수 있습니다. 그 후 한번 더 분할합니다.
이번에는 1 사분면에 위치하는 것을 알 수 있습니다. 정리해보면 4 사분면->2 사분면->1 사분면으로 이동한 것을 알 수 있고 n이 1인 경우이므로 여기서 분할은 종료가 됩니다.
맨 처음에 4 사분면에 위치하고 4행 6열이 그 다음에는 2사분면에 위치하고 0행 2열이 됩니다. 그 후 1사분면의 0행 0열로 위치가 바뀌므로 우리는 사분면을 나눌때마다 좌표를 재배치 해줘야하는것을 알 수 있습니다. 따라서 reallocate()를 정의하여 해결해줍니다.
문제 해결을 위한 팁
이번에는 reallocate함수를 자세하게 알아봅시다. 위의 예시를 그대로 이용하겠습니다.
4사분면에 위치한 4행 6열이 2 사분면으로 이동할 때 0행 2열이 되었습니다. 따라서 각각 4 만큼씩 줄어들었습니다.
이후 0행 2열이 0행 0열이 되었는데 이번에는 열만 2 만큼이 줄어든 것을 알 수 있습니다. 따라서 이를 일반화하면 다음과 같습니다.
1 사분면인 경우 -> 유지
2 사분면인 경우 -> 열 값만 2^(n-1)만큼 감소
3 사분면인 경우 -> 행 값만 2^(n-1)만큼 감소
4 사분면인 경우 -> 행 열 모두 2^(n-1)만큼 감소
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
n, r, c = map(int, input().split())
def find(r, c): # 사분면 찾는 함수
if 0 <= r < 2 ** (n-1) and 0 <= c < 2 ** (n-1):
return 1
elif 0 <= r < 2 ** (n-1) and 2 ** (n-1) <= c < 2 ** (n):
return 2
elif 2 ** (n-1) <= r < 2 ** (n) and 0 <= c < 2 ** (n-1):
return 3
else:
return 4
def reallocate(): # 사분면을 쪼갠후 좌표값을 재배치
global r, c, n
if res == 2: # 2사분면인 경우
c -= 2 ** (n-1)
elif res == 3: # 3사분면인 경우
r -= 2 ** (n-1)
elif res == 4: # 4사분면인 경우
r -= 2 ** (n-1)
c -= 2 ** (n-1)
n -= 1
ans = 0
while True:
if n <= 0:
break
res = find(r, c)
ans = ans + (res-1) * (4 ** (n-1))
reallocate()
print(ans)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1504: 특정한 최단 경로(Python) (0) | 2021.02.23 |
|---|---|
| 백준 알고리즘 1068: 트리(Python) (0) | 2021.02.21 |
| 백준 알고리즘 13459: 구슬 탈출(Python) (0) | 2021.02.19 |
| 백준 알고리즘 13460: 구슬 탈출 2 (Python) (1) | 2021.02.19 |
| 백준 알고리즘 9012: 괄호 (Python) (0) | 2021.02.06 |