코드

n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int, input())))

# 압축 함수
def comp(x, y, n):
    
    # 0, 1 둘 밖에 없으니까 
    # 입력받은 좌표의 값을 기준으로
    # 다음 값이 0인지 1인지 구분할 수 있음
    color = graph[x][y]
    
    for i in range(x, x+n):
        for j in range(y, y+n):
            
            # 색이 다르면 4등분 실시
            # 출력 순서 주의
            if color != graph[i][j]:
                print('(', end='')
                comp(x, y, n//2)
                comp(x, y+n//2, n//2)
                comp(x+n//2, y, n//2)
                comp(x+n//2, y+n//2, n//2)
                print(')', end='')
                return
    
    # 밑의 조건문이 실행이 됐다는 것은
    # 반복문 안의 return이 실행 되지 않았다는 의미
    # 즉, 분할한 부분의 모든 숫자가 같은 숫자라는 뜻
    if color == 0:
        print('0', end='')
        return
    else:
        print('1', end='')
        return
    
comp(0, 0, n)

문제 해설

쿼드 트리

분할 정복 문제이다. 개인적으로 분할 정복 문제 유형은 난이도 자체는 어렵지 않으나, 구현을 하는 부분에 있어서 경험치가 많이 중요하다고 느껴진다.

Z 문제

이전에 풀었던 Z 문제와는 달리 이 문제는 재귀를 이용하여 4등분을 실시하여 푸는 방식으로 접근하였다. 확실히 문제를 풀 때 생각하는 로직을 직접 그리고 글로 정리하면서 이를 코드로 옮겨 적으려 시도하니 좀 더 수월하게 문제를 풀 수 있는 것 같다.

댓글남기기

참고