1992

날짜 : 2023. 01. 31

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
graph = list()
for _ in range(n):
    t = sys.stdin.readline().rstrip()
    temp = list()
    for i in range(n): temp.append(int(t[i]))
    graph.append(temp)

res = list()


def check(row, col, len):
    num = graph[row][col]  # 기준이 되는 숫자
    for i in range(row, row + len): # 기준 노드부터 시작, 지정된 length만큼만 체크
        for j in range(col, col + len):
            if graph[i][j] != num:  # 안맞으면?? divide
                res.append("(")
                l = len // 2
                """check(row, col, l) # 왼-위
                check(row, col + l, l) # 오-위
                check(row + l, col, l) # 왼-아래
                check(row + l, col + l, l) # 오-아래"""
                # 둘 다 가능
                for a in range(2):
                    for b in range(2):
                        check(row + a * l, col + b * l, l)
                res.append(")")
                return
    res.append(num)
    return


check(0, 0, n)

# output 출력
for i in res:
    print(i, end="")

 

 

풀이

- 기준이 되는 노드의 숫자를 정한 후 해당 노드의 위치를 기준으로 이중 for문을 돌린다.

- 돌리는 도중 서로 다른 숫자가 나온다면 divide

- 총 4면(위-왼 / 위-오 / 아래-왼 / 아래-오)으로 분할하고, 탐색길이는 절반으로 줄어든다.

- 또한 분할할 때 괄호가 나와야 하기 때문에 결과를 출력할 리스트에 괄호를 넣고 재귀한다.

- 재귀를 탈출한 경우는 분할이 끝났을 때이기 때문에 괄호를 닫아주고 리턴한다.

- 분할이 이루어지지 않았을 때에는 정상적으로 아웃풋을 출력할 수 있는 경우이기 때문에 해당 노드의 숫자를 리스트 res에 push한다.

- (0, 0)부터 시작하고 탐색길이는 처음 입력받은 리스트의 가로길이이다.

- 탐색이 끝난 경우에는 출력한다.

 

 

알게된 점

- 중간 divide에서 for문을 돌리는 경우 결과값이 생략되지 않고 쭉 출력되는 결과가 나왔다.

- 왜 그럴까 계속 찾아보는데 명확한 답이 나오지 않아 조금 불편하다.

 

* 내가 실수했다.

check(row + a * l, col + b * l, l) 라고 코드를 썼어야 하는데

check(row + l, col + l, l) 이라고 하는 바람에 엉뚱한 아웃풋이 나왔다.

 

 

참고 사이트

-