[백준] [Class3] [Silver I] Z - 1074 (파이썬 / Python)

[Silver I] Z - 1074

문제 링크

성능 요약

메모리: 30616 KB, 시간: 36 ms

분류

분할 정복(divide_and_conquer), 재귀(recursion)

문제 설명

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

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

다음 예는 2² × 2² 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

# 나의 풀이 (Python3 36ms)

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

def dfs(r,c,start):
    global n
    if n == 1:                              # 최소 크기인 1x1에 도달한 경우 중단
        print(start)
    else:
        n //= 2
        if r < n and c < n:                 # 1사분면
            dfs(r, c, start)
        elif r < n and c >= n:              # 2사분면
            dfs(r, c-n, start+n**2)
        elif r >= n and c < n:              # 3사분면
            dfs(r-n, c, start+n**2*2)
        else:                               # 4사분면
            dfs(r-n, c-n, start+n**2*3)
dfs(r,c,0)

'''
TIL/회고
- map 대신 주어진 좌표를 가지고 풀기 때문에 익숙하지 않아 어려웠다.
- n을 2로 나눠주고 r과 c를 값을 n만큼 빼주면서 n==1 일 때 start값을 찾는다.
- 분할 정복 너무 어렵다..
'''

풀이

• 이번 문제는 익숙한 그래프가 아닌 좌표가 주어졌다.
• 어떻게 보면 DP처럼 큰 4분면에서 목표 위치를 찾아 다시 4분면으로 나눠 목표 위치를 찾는다.
• 주어진 N값은 배열의 크기인 2^N으로 초기화 시켜준다.
• 함수를 4가지로 케이스로 r과c와 그리고 시작좌표(start)를 넣어 분할 정복 재귀를 한다.
  • 시작좌표의 규칙은 n이 8일 때 n//=2를 통해 n은 4가되며 처음 값이 0,16,32,48 이면 0,n^2,(n^2)2,(n^3)3 이라는 규칙이 있다.

---

앞서 풀었던 분할 정복은 dfs알고리즘을 생각하고 이해하고 풀었지만 이 문제 같은 경우는 정말 순수 분할 정복 같은 느낌이 들었다. 이번 문제는 r과c를 n만큼 빼면서 재귀를 실행시키는 것 도 어려웠지만, Start의 규칙을 찾아 r과c행의 값을 찾는 방법이 정말 어려웠다. 알고 나면 쉬웠지만 DP를 어려워하는 나는 역시 규칙이 쉽게 떠오르지 않았다.. 분할 정복 언제쯤 정복하려나..🤣