백준 1992번: 쿼드트리 [python]

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

문제 접근

백준 2630번 색종이 접기와 비슷한 문제이다.

N*N 정사각형을 4사분면으로 4등분하여 0과 1을 압축하여 괄호와 0과 1로 표현하는 문제이다.

색종이 접기 문제에서 괄호 넣는 로직을 추가해주고 출력 순서를 바꿔주면 해결된다.

모르겠다면 색종이 4분할 문제를 다시 풀어보자

풀이 및 해답

import sys
input = sys.stdin.readline

N = int(input())
lst = [list(map(int, list(input().strip()))) for _ in range(N)]

result = []

def conquer(n, lst):
    if not any(1 in row for row in lst):
        result.append('0')
        return
    elif not any(0 in row for row in lst):
        result.append('1')
        return
    else:
        result.append('(')
        lst_0 = []
        lst_1 = []
        for row in lst:
            lst_0.append(row[:n//2])  # 왼쪽 절반 열
            lst_1.append(row[n//2:])  # 오른쪽 절반 열

        conquer(n//2, lst_0[:n//2])   # 왼쪽 위
        conquer(n//2, lst_1[:n//2])   # 오른쪽 위
        conquer(n//2, lst_0[n//2:])   # 왼쪽 아래
        conquer(n//2, lst_1[n//2:])   # 오른쪽 아래
        result.append(')')

conquer(N, lst)
print(''.join(result))

join 문법

리스트의 각 요소를 연결하면서 그 사이에 구분자를 넣음

chars = ['a', 'b', 'c']
print(''.join(chars))  # abc ,  ''사이에 있는게 구분자인데 아무것도 안넣어줘서 주욱 이어 붙여진것임.