[Python][백준] 1074. Z / 분할정복,재귀 (G5)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

N,row,col = map(int,input().split())

cnt = 0
def dfs(x,y,n):
    global cnt 
    if n == 1:
        if x == row and y == col:
            print(cnt)
        elif x == row and y+1 == col:
            print(cnt+1)            
        elif x+1 == row and y == col:
            print(cnt+2)            
        elif x+1 == row and y+1 == col:
            print(cnt+3)            
        return 
    
    gap = 2 ** (n-1)
    x_gap,y_gap = x+gap,y+gap
        
    if x<=row<x_gap and y<=col<y_gap:
        dfs(x,y,n-1)
    elif x<=row<x_gap and y_gap<=col:
        cnt += (gap**2)
        dfs(x,y_gap,n-1)
    elif x_gap<=row and y<=col<y_gap:
        cnt += (gap**2)*2
        dfs(x_gap,y,n-1)
    elif x_gap<=row and y_gap<=col:
        cnt += (gap**2)*3
        dfs(x_gap,y_gap,n-1)

dfs(0,0,N)

 

1. 재귀함수를 통해 입력받은 row와 col이 몇 사분면인지를 먼저 확인해줘야 한다. 

gap 변수를 간격으로 설정해여, 위와 같은 코드를 작성했다.

 

간격을 설정해두고 재귀를 돌리는게 복잡해 보일 수 있는데,

이와 비슷한 문제들이 많으니 해당 방식을 잘 기억해두면 좋을 것 같다. 

 

2. 끝까지 재귀를 타면 n = 1 이 되어 있을 것이다. 

여기에서 (Z에 해당되는) 4가지 조건문을 만들어서 해당되는 구문을 출력해준다.

 

📌 내가 썼던 코드 

import sys
sys.stdin = open("input.txt", "r")
sys.setrecursionlimit(100000) 
import psutil

N,r,c = map(int,input().split())
graph = [[0] * (2**N) for _ in range(2**N)]
cnt = 0 

def memory_usage(message: str = 'debug'):
    # 현재 램 사용량
    p = psutil.Process()
    rss = p.memory_info().rss / 2 ** 20 # Bytes to MB
    print(f"[{message}] memory usage: {rss: 10.5f} MB")


def dfs(N,x,y):
    global cnt
    if N == 1:
        graph[x][y] = cnt + 0 
        graph[x][y+1] = cnt + 1
        graph[x+1][y] = cnt + 2 
        graph[x+1][y+1] = cnt + 3
        cnt += 4
        return 

    gap = 2**(N-1)
    dfs(N-1,x,y)
    dfs(N-1,x,y+gap)
    dfs(N-1,x+gap,y)
    dfs(N-1,x+gap,y+gap)

dfs(N,0,0)
print(graph[r][c])

dfs(N,0,0)
memory_usage('#1')

 

내가 작성한 코드이고 추가로 현재 램 사용량까지 확인 해보았다. 

해당 방식은 답은 맞지만 메모리가 초과된 코드이다.

 

 

N의 범위는 N<=15인데 겨우 N=12만 해도 메모리가 메모리 제한을 초과하는 것이다.  

 

내가 작성한 코드를 보면 상당히 비효율적이다. 

해당 문제에서는 특정 값만 요구하는데,

코드에서는 모든 배열을 완성시키고 출력한다.  

 

dfs에서 리스트를 갱신해주는 것은 조심스럽다 ...

 

이런 특정 값만 요구하는 문제 같은 경우,  

시간, 공간 복잡도들을 고려해서 특정값만 추출 할 수 있도록 해보자.

---

📚문제

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

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

예제 입력 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