[백준] 1992 쿼드트리 (파이썬/python)

🎈문제

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

 

🎁어떤 알고리즘?

1. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 총 4개의 영역을 압축한다는 부분에서 분할 정복, 재귀 알고리즘임을 깨달았다.

 

 

💻코드

# 1992 쿼드트리

# 3. 영상 압축 합수 만들기
# x: 세로, y: 가로
def compress(x,y,n):
    start = video[x][y] # 시작 지점의 색 저장해두기
    for i in range(x,x+n):
        for j in range(y,y+n):
            if video[i][j] != start:    # 다른색 나오면
                start = -1
                break

    if start == -1:
        print('(',end='')
        div_n = n//2    # 4개의 영상으로 나누기
        # 4 부분 모두 재귀로 확인
        compress(x,y,div_n) # 1번째 영역 (0,0)
        compress(x,y+div_n,div_n)   # 2번째 영역 (0,1)
        compress(x+div_n,y,div_n)   # 3번째 영역 (1,0)
        compress(x+div_n,y+div_n,div_n) #4번째 영역 (1,1)
        print(')',end='')
    elif start == 1:
        print(1,end='')
    else:
        print(0,end='')

# 1. 영상 크기 입력 받기
n = int(input())

# 2. 영상 입력 받기
video = []
for i in range(n):
    video.append(list(map(int,input())))

result = [] # 압축 결과 저장 변수

# 4. 영상 압축
compress(0,0,n)

 

🎄코드 설명

1. 분할 정복 문제를 몇번 풀어보면, 이 알고리즘은 어느정도 틀이 잡혀있다는 것을 알 수 있다. 구조를 외워두자

2. 시작지점의 색을 저장해두고, 2중 for문을 모두 돌면서 모두 같은 색인지, 다른 색이 있는지 판단을 먼저 한다.

3. 다른 색이 있을 경우 4개의 영역으로 나눠서 각각 재귀적으로 4개의 영역에 다른색이 있는지를 판단하는 것을 반복한다.