[Python] 백준 풀기 1992 - 쿼드트리

파이썬 백준 1992번

실버1

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

1992번: 쿼드트리

 

 

 

문제 보기

분류: 분할 정복, 재귀

 

 

 

문제 풀기

이전에 풀었던 2630번 색종이 만들기 문제와 거의 동일하다.

https://xcevor.tistory.com/56

[Python] 백준 풀기 2630 - 색종이 만들기

출력되는 형식만 잘 지켜주면 되는데 재귀 함수를 들어갈때  "(" 와 나올때 ")" 가 프린트 되도록 해주고, 압축된 결과에 대해 0 또는 1 이 프린트 되도록 한다.

 

거의 비슷한 문제를 한번 더 풀었지만 왠지 이런 문제를 접근하는 방식에 대해 조금 훈련이 된듯하다.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnCompressor(x, y, N):
    wb_check = wbscreen_ls[x][y]
    for i in range(x, x + N):
        for j in range(y, y + N):
            if wb_check != wbscreen_ls[i][j]:
                print("(", end='')
                fnCompressor(x, y, N//2)
                fnCompressor(x, y + N//2, N//2)
                fnCompressor(x + N//2, y, N//2)
                fnCompressor(x + N//2, y + N//2, N//2)
                print(")", end='')
                return

    if wb_check == 0:
        print(0, end='')
    if wb_check == 1:
        print(1, end='')


if __name__ == "__main__":
    N = int(inputdata().strip())
    wbscreen_ls = [list(map(int, inputdata().strip())) for _ in range(N)]
    
    # print(wbscreen_ls)
    
    fnCompressor(0, 0, N)



# 8
# 11110000
# 11110000
# 00011100
# 00011100
# 11110000
# 11110000
# 11110011
# 11110011

# ((110(0101))(0010)1(0001))