Algorithm/Baekjoon
BOJ 1992 쿼드트리 python3
Bonita SY
2023. 6. 22. 11:14
728x90
https://www.acmicpc.net/problem/1992
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
import sys
input = sys.stdin.readline
N = int(input())
video = [input().rstrip() for _ in range(N)]
result = ""
def checkVideo(video, num):
global result
if num < 2:
value = video[0][0]
result += value
return
stdValue = None
isBreak = False
for i in range(num):
for j in range(num):
if stdValue == None:
stdValue = video[i][j]
elif stdValue != video[i][j]:
isBreak = True
break
if isBreak:
break
if isBreak:
newNum = num // 2
if num == 2:
value = "(" + video[0][0] + video[0][1] + video[1][0] + video[1][1] + ")"
result += value
return
result += "("
leftTopVideo = []
for x in range(0, newNum):
elems = []
for y in range(0, newNum):
elems.append(video[x][y])
leftTopVideo.append(elems)
checkVideo(leftTopVideo, newNum)
rightTopVideo = []
for x in range(0, newNum):
elems = []
for y in range(newNum, num):
elems.append(video[x][y])
rightTopVideo.append(elems)
checkVideo(rightTopVideo, newNum)
leftBottomVideo = []
for x in range(newNum, num):
elems = []
for y in range(0, newNum):
elems.append(video[x][y])
leftBottomVideo.append(elems)
checkVideo(leftBottomVideo, newNum)
rightBottomVideo = []
for x in range(newNum, num):
elems = []
for y in range(newNum, num):
elems.append(video[x][y])
rightBottomVideo.append(elems)
checkVideo(rightBottomVideo, newNum)
result += ")"
else:
value = stdValue
result += value
return
checkVideo(video, N)
print(result)
728x90