[Algorithm] 백준 BOJ 1074 Z python 파이썬 분할정복 실버1

Private 난이도 : ♥♥♥♡♡

1074번: Z

시간초과 코드

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

graph=[[0 for _ in range(size)] for _ in range(size)]
cnt=0
dr=[0,0,1,1]
dc=[0,1,0,1]
def divide(r,c,size):
    global cnt
    if size==2:
        for i in range(len(dr)):
            graph[r+dr[i]][c+dc[i]]=cnt
            cnt+=1
    else:
        size//=2
        divide(r,c,size)
        divide(r,c+size,size)
        divide(r+size,c,size)
        divide(r+size,c+size,size)

divide(0,0, size)
print(graph[r][c])

맞은 코드

import sys
n,target_r,target_c=map(int,sys.stdin.readline().split(' '))
size=2**n

graph=dict()
cnt=0 # 답이 될 포인터

# Z순서대로 : 왼위,오위,왼아래,오아래
dr=[0,0,1,1] 
dc=[0,1,0,1]

# 1,2,3,4 사분면(4등분했을 때)으로 나누었을 때 어디에 있는지 확인
def check_quad(r,c,now_r,now_c,size):
    rr=now_r+size//2
    cc=now_c+size//2
    if r<rr and c<cc: # 1사분면
        return 0
    elif r<rr and c>=cc: # 2사분면
        return 1
    elif r>=rr and c<cc: # 3사분면
        return 2
    elif r>=rr and c>=cc: # 4사분면
        return 3

def divide(r,c,size):
    global cnt
    if size==2: # 한 변의 길이가 2가 될 때만 graph에 그린다
        for i in range(4):
            graph[(r+dr[i],c+dc[i])]=cnt
            cnt+=1
    else:
        flag=check_quad(target_r,target_c,r,c,size) # 사분면 체크
        size//=2
        
        cnt+=size*size*flag # 진짜로 graph에 그리지 않고 cnt를 더해서 skip해줌

        plus=[[0,0],[0,size],[size,0],[size,size]] # 다음 분할을 위한 위치를 사분면에 따라 다르게 해줌
        divide(r+plus[flag][0], c+plus[flag][1], size)

divide(0,0, size)
print(graph[(target_r,target_c)])

 

설명

• 그림에서 노랑색 글씨,빨강 글씨
  

   cnt+=size*size*flag

• 전체 그래프를 다 채우는 방식으로 했더니 시간초과
• 어차피 원하는 좌표가 처음부터 나와 있으니 그 부분만 계산하는 방식으로 바꾸고자함
• cnt를 포인터처럼 사용해서  cnt를 점점 늘려주어 그 수에 다가가고 마지막 2*2 만큼까지 줄어들었을 때 그래프를 그림으로써 문제 해결
• check_quad를 통해 현재 사각형 내에서 어느 사분면에 위치하는 지를 반환함으로 재귀를 4개를 부르는 것에서 하나 부르는 것으로 줄임
• 메모리초과 해결
  • 연산 줄이기
    

    #######1
    if r<now_r+size//2 and c<now_c+size//2:
        return 1
    elif r<now_r+size//2 and c>=now_c+size//2:
        return 2
    elif r>=now_r+size//2 and c<now_c+size//2:
        return 3
    elif r>=now_r+size//2 and c>=now_c+size//2:
        return 4
        
    ########2
    rr=now_r+size//2
    cc=now_c+size//2
    if r<rr and c<cc:
        return 0
    elif r<rr and c>=cc:
        return 1
    elif r>=rr and c<cc:
        return 2
    elif r>=rr and c>=cc:
        return 3

    매번 if문 들어갈 때 마다 now_c_size//2 라는 연산을 하게 되는 것 같아서 연산시에
    1) size//2
    2) now_c+size//2라는 두 결과를 계산할 때마다 메모리를 차지할까봐 싶어서 바꾸었다
  • flag 연산 줄이기
    처음에는 내가 이해하기 쉽도록 1,2,3,4 사분면이라고 칭하고 indexing할 때 -1을 해서 가져오도록 했다
    

    # 처음
    divide(r+plus[flag-1][0], c+plus[flag-1][1], size)
    # 변경 후
    divide(r+plus[flag][0], c+plus[flag][1], size)

    하지만 또 flag-1이라는 결과를 매번 저장하고 연산하는데 시간이 들까봐 0,1,2,3으로 바꾸어 주었다
  • range(len(dr)) -> range(4)
    사실 dr의 전체 길이가 바뀔 일이 없어서 4로 넣어도 무방한 건 알고 있으나 그냥 저렇게 4로 써주는 것이 뭔가 위험해 보여서 지금까지 일부로 len을 사용했었는데 여기에서는 또 len(dr)을 어디에 저장하고 있을까봐 줄여주었다
  • graph를 list -> dict
    이 부분이 메모리초과의 주원인 이었을 것이라고 생각한다.
    처음에 문제를 graph를 전체를 채운 후에 그 부분의 값만 가져오려고 했기 때문에 graph를 2**n * 2**n의 크기만큼으로 할당했었다. 하지만 필요한 부분만 타겟팅해서 가져오기 때문에 이제 그렇게는 필요 없어서 graph의 좌표를 tuple로 해서 dictionary의 key로 넣었다.

배운 점

• 문제를 보면 시간 한 번 계산 하고 문제를 어떻게 풀지 설계해야겠다고 생각했다.