[ACM-ICPC Baek Joon] Quadtree

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

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

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

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

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