[백준] 1074번 Z (Python)

정답 코드 및 풀이는 맨 아래에 있습니다.

https://www.acmicpc.net/problem/1074

• 사고력을 요하는 재귀문제였다. 구상하는데 적당한 난이도가 있었고, 구현하는데도 적당한 난이도가 있었다.

---

< Z > 

[문제]

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

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

---

아이디어

한 보드를 네 칸으로 나누어 몇 번째 칸인지를 구하고, 그 칸에서 또 몇 번째 칸인지 구하고 ... 이를 특정 계산을 통해 모두 더해주면 된다.

풀이 및 코드

# 0, 1, 2, 3번째 구역 중 어디인지 찾는 함수
def findZoneLocation(len, r, c):
    zone = 0
    if (len // 2) <= r:
        zone += 2
    if (len // 2) <= c:
        zone += 1
    return zone

def recFindLocation(len, r, c):
    if len == 1:
        return 0
    # 작은 칸으로 갈 때 그 칸 중 몇 번째 행, 열인지 저장
    # 예를 들면 len = 8, r = 7, c = 7이면 다음 재귀에서 len = 4, r = 3, c = 3을 인자로 넣어줌
    new_r = r if r < (len // 2) else r - (len // 2)
    new_c = c if c < (len // 2) else c - (len // 2)
    # len이 8인 보드를 4구역으로 나누면 한 구역의 크기는 4 ** 2 = 16
    # 따라서 16 * 구역 위치(0, 1, 2, 3) + 작은 칸의 위치(재귀)를 리턴해준다.
    return ((len // 2) ** 2) * findZoneLocation(len, r, c) + recFindLocation(len // 2, new_r, new_c)

n, r, c = map(int, input().split())
print(recFindLocation(2 ** n, r, c))

findZoneLocation(8, 7, 7)이라고 생각해보자. r = 7은 len // 2보다 크므로 zone += 2이고, c = 7은 len //2 보다 크므로 zone += 1이다. 따라서 zone = 3이 된다.

recFindLocation(8, 7, 7)이라고 생각해보자. (len // 2) ** 2는 4^2이므로 16이다. findZoneLocation을 곱해주어, 즉 16 * 3을 더해주는 것이다. 이 의미는 앞의 세 구역의 칸의 개수를 모두 더해준다는 의미이다. 

그 뒤에 recFindLocation(len // 2, new_r, new_c)는 다시 작은 구역에서 계산하라!라는 의미로, 같은 함수를 재귀적으로 호출한 것이다. 재귀적으로 호출하는 함수의 인자로는 4, 3, 3이 들어가게 된다. 이 함수로 들어가게 되면 다시 길이가 4인 보드에서 3, 3의 위치에 대해 리턴하게 된다.

다음 보드를 네 구역으로 나누어 앞의 세 구역의 칸의 개수를 모두 더해주고 다시 재귀 함수로 들어가게 된다. 이를 반복하다 보면 칸의 위치를 알 수 있다.

후기

오랜만에 재귀함수 문제를 풀어보아서 머리를 조금 썼던 문제였다. 수학적 요소도 있고, 프로그래밍 요소도 있어 나에게는 재귀함수 문제만큼 재미있는 게 없는 것 같다. 실제로 대학교 과제 할 때에도 재귀를 많이 썼을 정도로, 나에게는 재귀가 정말 재미있고 소중하다.

이제 더 어려운 난이도의 문제를 풀러 가야겠다~