[알고리즘][Python] 백준(BOJ) 1992 쿼드트리_파이썬

 

1992 쿼드트리    www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

 

문제 풀기 전 공부할 것 : 분할 정복

 

 

 

 

 

 

 

풀이

<내용>

• 영상이 모두 같은 점으로 되어 있는지 확인하는 check 함수를 정의한다.
• solve 함수를 통해 점 1개를 확인하는 경우 그 점을 결과에 추가한다.
• 점 1개가 아닌 경우 check 함수를 통해 같은 점으로 되어 있는지 확인한다.
• 같은 점이 아니라면 결과에 '('를 추가하고 영상을 나누는 작업을 진행한 후 ')'를 추가한다.
• 같은 점이라면 해당 점을 결과에 추가한다.

 

 

<코드>

import sys
input = sys.stdin.readline

n = int(input())
image = [list(map(int, input().rstrip())) for _ in range(n)]
res = ''

def check(i, j, d):
    std = image[i][j]
    for x in range(i, i+d):
        for y in range(j, j+d):
            if image[x][y] != std:
                return -1
    return std

def solve(i, j, k):
    global res
    
    if k == 1:
        res += str(image[i][j])
        return
    
    chk = check(i, j, k)
    if chk == -1:
        res += '('
        k //= 2
        for p in range(2):
            for q in range(2):
                solve(i+p*k, j+q*k, k)
        res += ')'
    else:
        res += str(chk)
    return

solve(0, 0, n)
print(res)

 

 

 

 

 

 

 

 

비슷한 문제

2020/11/23 - [Algorithm/백준 알고리즘] - [알고리즘][Python] 백준(BOJ) 2630 색종이 만들기_파이썬

[알고리즘][Python] 백준(BOJ) 2630 색종이 만들기_파이썬