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

 

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

1992번: 쿼드트리

---

풀이

이 문제는 재귀함수를 이용해 해결하였다.

우선 

1. 분할한 사각형안이 전부 같은 숫자인지 확인한다.(11~19)

   사각형의 첫 인덱스값을 ch에 대입한 다음, for문을 돌면서 범위안의 다른 값과 비교한다.

   만약 다르면 check값을 False로 바꾸고 break로 for문을 빠져나온다.

2. for문이 다돌고 check값이True로 바뀌지 않았다면 ch값을 ans배열에 저장

   check값이 False로 바꼇다면 해당 사각형안의 인덱스 값이 다른게 있으므로 

   재귀 함수를 이용하여 분할된 사각형을 다시 분할함.

n=int(input())
arr=[]
ans=[]
for i in range(n):
    arr.append(list(map(int, input())))
 
def Cal(n,x,y):
    if n==1:
        ans.append(arr[x][y])
        return
    check=True
    ch=arr[x][y]
    for k in range(x,x+n):
        for l in range(y,y+n):
            if arr[k][l]!=ch:
                check=False
                break
        if check==False:
            break
    if check==True:
        ans.append(ch)
    else:
        a = n // 2
        ans.append('(')
        for i in range(2):
            for j in range(2):
                Cal(a,x+a*i,y+a*j)
        ans.append(')')
Cal(n,0,0)
print(''.join(str(i) for i in ans))