[백준] 1992번 : 쿼드트리

 

 

 

 

 

 

 

접근법

- 이전에 풀어봤던 2630번과 거의 동일한 메커니즘으로 풀었다.

 

- 기본적으로 동작 원리는 N만큼을 검사해서 동일한 숫자로만 놓여있으면 그 숫자를 찍고, 그렇지 않으면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 차례로 검사하여 압축 결과를 괄호 안에 찍는 방식이다.

 

- 전과 다른 점은 이 4 분할된 영상을 ()로 에워싸야 하는 것과, 왼쪽 위, 왼쪽 아래, 왼쪽 아래, 오른쪽 아래를 순차적으로 검사해야 한다는 것이다. 이 과정은 단순히 생각해보면, 4 분할하는 곳의 앞뒤로 print("(", end=""), print(")", end="")을 각각 추가해주면 끝이 난다.

 

- 전과 로직 자체가 거의 차이 없는 쉬운 문제인데 왜 2단계나 난이도 차이가 있는지 잘 모르겠다.

 

- 이 문제를 풀면서 valueError로 인해 고생을 많이 했다. sys를 import한 후에 input = sys.stdin.readline으로 지정하고 N = int(input()), paper = [list(map(int, input())) for _ in range(N)]으로 설정했다. 이 부분에서 런타임 에러(valueError)가 발생했는데 찾아보니 "readline은 EOF를 만났을 때 EOFError 대신 빈 문자열을 반환하므로, 이를 int로 변환할 때 ValueError가 발생합니다." 이런 문제점이 있다고 한다. 

 

 

 

 

 

 

 

풀이

N = int(input())
paper = [list(map(int, input())) for _ in range(N)]

def check(i, j, n) :
    temp = paper[i][j]
    for x in range(i, i + n) :
        for y in range(j, j + n) :
            if paper[x][y] != temp :
                return False
    return True

def quad_tree(i, j, n) :
    if check(i, j, n) :
        print(paper[i][j], end="")
        return
    else :
        print("(", end="")
        quad_tree(i, j, n // 2)
        quad_tree(i, j + n // 2, n // 2)
        quad_tree(i + n // 2, j, n // 2)
        quad_tree(i + n // 2, j + n // 2, n // 2)
        print(")", end="")
        return

quad_tree(0, 0, N)

 

 

 

 

 

 

 

결과