[알고리즘 일기 - 파이썬] 198. Z

문제 198. (2022-02-28)

 

1074번: Z

Baekjoon 1074. Z

[파이썬(python) - 분할정복]

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

 

---

입력 예시

2 3 1

 

---

출력 예시

11

 

---

❧ 정답

🔎IDEA) 분할정복 - 재귀를 반복하는 포인트를 중간 좌표로 잡는다.

• Z 함수 : z 그리는 함수
• 파라미터 설명
  • n : 사각형의 크기 (n 제곱)
  • x, y : 가운데 지점의 좌표
  • total : 지금까지 방문한 지점들의 거리 총합

[Line 16 - 23]

• 현재 중간지점의 좌표(x, y)와 찾고자하는 좌표 (r, c)를 비교하여 범위를 좁혀들어간다.

#16

1. 만약 r < x and c < y 라면 현재 탐색을 진행하는 사각형(x, y)의 2사분면 내부에 (r, c)가 위치하므로
total 값은 증가시키지 않은 채 z함수에 대한 재귀를 수행한다.

#18

2. 만약 r < x and c >= y 라면 현재 탐색을 진행하는 사각형(x, y)의 1사분면 내부에 (r, c)가 위치하므로
2사분면에 대한 탐색을 진행했다고 보고 사각형의 1/4 크기만큼 total에 증가시킨 뒤, z함수에 대한 재귀를 수행한다.

#20
3. 만약 r >= x and c < y 라면 현재 탐색을 진행하는 사각형(x, y)의 3사분면 내부에 (r, c)가 위치하므로
2, 1사분면에 대한 탐색을 진행했다고 보고 현재 사각형의 2/4 크기만큼 total에 증가시킨 뒤, z함수에 대한 재귀를 수행한다.

#22
4. 만약 r >= x and c >= y 라면 현재 탐색을 진행하는 사각형(x, y)의 4사분면 내부에 (r, c)가 위치하므로
2, 1, 3사분면에 대한 탐색을 진행했다고 보고 현재 사각형의 3/4 크기만큼 total에 증가시킨 뒤, z함수에 대한 재귀를 수행한다.

[Line 6 - 14]
👉 만약 n이 1이라면 ( ${2^1}$ )
(r, c)의 좌표 범위를 최대한으로 좁혀들어갔으므로 다시 현 사각형에서 1, 2, 3, 4분면 중 어느 부분에 속하는 지 구분한 뒤 total 에 해당 위치만큼 1, 2, 3을 증가시킨 뒤 total을 출력한다.