[ACM-ICPC Baek Joon] Quadtree

본 문제는 쿼드트리라는 일종의 압축기법에 대한 문제이다. 쿼드트리의 규칙에 맞게 압축하여 결과물을 출력하는 코드를 작성하면 된다. 

문제는 "acmicpc.net"의 1992번 문제[1]이며 원문은 아래와 같다. 

쿼드트리라는 기법에 대한 자세한 설명은 위키피디아[2]에 있으니 필요하다고 생각될 경우 참고하면 좋을 것 같다.

그리고 내가 작성한 코드는 아래와 같다. 

constQueue = list()

def makeSqure(mData):
	oData = list()
	sNum = 0
		
	for n in range(1, 64):
		sNum = len(mData)/n
		if sNum == n: break
	
	j = 0
	oData.append(list())
	for i in range(len(mData)):
		if i%sNum == 0:
			oData.append(list())
			j = j+1
		oData[j].append(mData[i])

	del oData[0]
			
	return oData


def all_01(sData, mN): 

	cList = list() 
	for i in range(mN):
		for j in range(mN):
			cList.append(sData[j][i])

	if len(list(set(cList))) != 1:
		sepData0 = list()
		sepData1 = list()
		sepData2 = list()
		sepData3 = list()

		for i in range(mN):
			for j in range(mN):
				if i < mN/2 and j < mN/2:
					sepData0.append(sData[i][j])
				elif i < mN/2 and j >= mN/2:
					sepData1.append(sData[i][j])
				elif i >= mN/2 and j < mN/2:
					sepData2.append(sData[i][j])
				elif i >= mN/2 and j >= mN/2:
					sepData3.append(sData[i][j])


		constQueue.append("(")
		all_01(makeSqure(sepData0), mN/2)
		all_01(makeSqure(sepData1), mN/2)
		all_01(makeSqure(sepData2), mN/2)
		all_01(makeSqure(sepData3), mN/2)
		constQueue.append(")")

	else:
		constQueue.append(str(cList[0]))
	
if __name__=="__main__":
	N = int(input())
	if N == 0:
		exit()

	scene = list()
	for n in range(N):
		ln = str(raw_input())
		scene.append([ln[n] for n in range(len(ln))])

	all_01(scene, N)

	print "".join(constQueue)

P.S. 큐나 스텍 같은 자료구조를 이용해 출력했다면 더 고급스러워 보였겠지만, 귀찮음으로 인해 그냥 전역변수 리스트를 하나 사용했다.....

References:

[1] https://www.acmicpc.net/problem/1992

[2] https://en.wikipedia.org/wiki/Quadtree