[BOJ] 1992 : 쿼드트리 [분할](Python)

문제 링크

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

소스 코드

import sys
input = sys.stdin.readline

n = int(input().rstrip())

graph = [] # 그래프 입력받기
for i in range(n):
    graph.append(list(map(int,input().rstrip())))

def dfs(x,y,n):
    if n == 1: # 최소 사각형인 경우 바로 추가
        answer.append(graph[x][y])
        return
    
    # 기준이 되는 숫자(사각형 왼쪽 맨 위)
    stand = graph[x][y]
    for i in range(x,x+n): # 범위 유의
        for j in range(y,y+n):
            # 기준과 다른 숫자가 나오면
            if graph[i][j] != stand:
                n //= 2 # 4분할 탐색
                answer.append('(')
                dfs(x,y,n) # 왼쪽 위
                dfs(x,y+n,n) # 오른쪽 위
                dfs(x+n,y,n) # 왼쪽 아래
                dfs(x+n,y+n,n) # 오른쪽 아래
                answer.append(')')
                return
    
    # 사각형이 한 숫자로만 이루어진 경우
    answer.append(stand)
    return

answer = []
dfs(0,0,n) # (0,0)에서 시작

# answer의 모든 원소를 공백 없이 출력
print(*answer,sep='')

 

해설

• 다른 숫자가 포함되는 경우 4분할 탐색
• 괄호의 위치

주어진 그래프를 탐색하여 같은 숫자로만 구성되어있는지 확인하고, 다른 숫자가 포함되는 경우 4분할 탐색을 진행하는 것은 다른 문제와 완전히 동일한 알고리즘을 사용한다.

대표적인 분할 유형에 해당하는 문제다.

 

관건은 '괄호를 어느 위치에 배치해야 하는가'이다.

문제를 풀이하면서 정확히 이런 논리 때문에 이 위치에 괄호를 열고 닫아야겠다고 파악하는 것은 굉장히 어려운 것 같고, 

가능할 것 같은 위치에 하나씩 괄호를 추가해보면서 원하는 결과가 나오는지 확인하는 것이 중요한 것 같다.

 

DFS 수행 과정: 4분할 탐색

우선 dfs로 정의한 함수는 다음과 같이 작동한다.

 

1) n이 1인 경우, 추가 탐색할 필요 없이 바로 graph[x][y]를 추가하고 함수를 종료한다.

n이 1이라는 것은 마지막 탐색을 수행중이라는 뜻이다. 가장 작은 사각형을 보고 있으므로 더이상 분할할 수 없다.

 

2) 기준이 되는 숫자를 변수에 저장한다.

우리가 확인해야 하는 것은 사각형이 전부 같은 숫자로 구성되어 있는지의 여부다.

따라서 기준이 되는 숫자를 graph[x][y] 에서 꺼내와 저장한다.

 

3) 범위에 맞는 사각형을 탐색하며 기준과 다른 숫자가 있는지 찾는다.

3-1) 모두 같은 숫자로 구성된 경우

이때는 이중 for문 내에 포함된 if 조건문에 걸리지 않는다. 따라서 그대로 기준 숫자를 answer에 추가하고 함수가 종료된다.

 

3-2) 다른 숫자가 포함된 경우

사각형 내 기준 숫자와 다른 것이 하나라도 발견되면 그 즉시 n을 2로 나누고 4분할 탐색을 실시한다.

n이 절반으로 줄었으므로 x와 y, 즉 행과 열의 시작점을 잘 구분해서 dfs를 실행한다.

 

이때 주의할 것은 순서다.

문제에서 제시한 탐색 순서는 '왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래'이므로 재귀 함수를 실행할 때도 이 순서에 맞춰 매개변수를 전달한다.

 

다른 숫자가 하나라도 포함된 것이 발견되어 4분할 탐색을 돌리고 바로 함수를 종료한다.

이후의 숫자들 중 다른 것이 발견되어 중복 작업을 실시하거나, 2의 제곱수가 아닌 위치에서 분할 탐색이 수행되는 것을 방지하기 위함이다.

 

괄호의 위치

중요한 것은 괄호의 위치다. 문제에서 주어진 예시를 잘 살펴보며 최대한 이해를 해본다.

 

괄호는 4분할이 시작되는 위치에서 열린다 '('.

만약 4분할을 이후 탐색을 수행하는 도중 또 4분할을 실시해야 하면 괄호를 새로 추가한다.

 

4분할 탐색이 종료되면 어쨌든 해당 탐색에 대해서는 더이상 다룰 것이 없으므로 괄호를 닫아준다 ')'.

아직 재귀함수가 모두 종료되지 않았다면 나머지도 모두 처리되면서 괄호를 닫게 된다.

 

결과적으로 가장 바깥부터 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 압축하며 괄호를 닫아줄 수 있게 된다.

 

 

처음 언급했던 것처럼 괄호를 추가하는 위치는 직접 출력해보면서 적당한 곳을 찾아가는 것이 직관적으로 이해하는데 가장 도움이 된다.