오늘의 문제 - boj-1992

문제

풀이

분할정복, 재귀문제다. 현재의 row, col 그리고 n값을 받아와 row부터 row + n , col부터 col+n 까지의 movies 값 전체가 하나로 일치하는지 검사하고 일치한다면 그 값을 반환해주고 아니라면 순서대로 2사분면 , 1사분면, 3사분면, 4사분면 순으로 다시 압축을 시도하면 된다.

"(" + str(get_quad_tree_value(r, c, n//2))\
    + str(get_quad_tree_value(r, c + n//2, n//2))\
    + str(get_quad_tree_value(r +n//2, c, n//2))\
    + str(get_quad_tree_value(r+n//2, c+n//2, n//2)) + ")"

위와 같이 리턴값을 설정해주면 순서대로 압축된 값을 괄호안에 반환하게 된다.

N = int(input())
movies = [list(map(int, list(input()))) for _ in range(N)]
answer = []
def is_whole_array_equal(r,c,n):

    cur_scene = movies[r][c]
    
    for i in range(r, r+n):
        for j in range(c, c+n):
            if movies[i][j] != cur_scene:
                return False
    return True

def get_quad_tree_value(r,c,n):
    if n == 0:
        return
    if not is_whole_array_equal(r,c,n):
        return "(" + str(get_quad_tree_value(r, c, n//2))\
    + str(get_quad_tree_value(r, c + n//2, n//2))\
    + str(get_quad_tree_value(r +n//2, c, n//2))\
    + str(get_quad_tree_value(r+n//2, c+n//2, n//2)) + ")"
    
    return movies[r][c]

print(get_quad_tree_value(0,0,N))

피드백

색종이 자르기 문제를 예전에는 손도 못 댔던 거 같은데 곧잘 풀게 됐다. 긍정적인 발전이다.

그러나 여전히 누군가에게 잘 설명하라고 하면 어려움이 조금 있다. 이유는 아직도 감으로 푸는 방식을 이해해서라고 생각한다. 수도코드 먼저 쓰고 작성하자