[분할정복] 백준 - 쿼드 트리 1992번

쿼드 트리 1992번

👏 key point: 대표적인 분할 정복 문제이다.자세한 것은 그림으로 설명하겠다.

이때, x는 w,b가 섞여있을때 나타낸 표시이다. (그림을 설명을 위해 퍼 온것이기 때문에 코드에서는 x에 대한 구현을 하지는 않을 것이다.)

분할 정복은 무엇인가?

우리는 재귀함수를 통해 수열이 1의 값이 될 때까지 분할한 후 병합하는 과정이다. 따라서 우리는 재귀함수를 통해서 제일 작은 사각형까지 분할한 후 그 다음 사각형(2X2)가 모두 하얀색인지 색이 섞여있는지 확인한다. 이런 식으로 (11) -> (22) 로 점점 병합하는 과정을 거친다. 자세한 건 코드를 통해 설명하도록 하겠다.

🎂 코드

n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(str, input())))

def check(y0,x0,y1,x1,n):
    # 수열의 길이가 1일 경우 종료
    if n == 1:
        return graph[y0][x0]

    # 병합
    a = n // 2

    r1 = check(y0,x0,y1+a,x1+a,a) #왼쪽 위
    r2 = check(y0,x0+a,y1-a,x1,a) #오른쪽 위
    r3 = check(y0+a,x0,y1,x1-a,a) #왼쪽 아래
    r4 = check(y0+a,x0+a,x1,y1,a) #오른쪽 아래

    # 해당 트리의 가지들을 삭제시킨다. 
    if r1 == r2 == r3 == r4 and len(r1) == 1:
        
        return r1

    return "(" +r1+r2+r3+r4 + ")"

print(check(0,0,n,n,n))     

우리는 if == 1: 즉 수열의 길이가 1이 될 때까지 분할 과정을 거칩니다.

분할 과정은 4개로 나뉠 수 있습니다.

이 때, 나누어진 4개의 항목의 길이가 1이고 4개가 모두 같다면 대표값 중 하나인 r1을 리턴합니다. 이것을 그림으로 표현하자면

즉, quad(,,,,n=2)의 return 값이 (wwww)였지만 if r1 == r2 == r3 == r4 and len(r1) == 1: 구문을 통해 같은 경우 리턴 값을 대표값인 w로 하여 밑에 있는 가지들을 모두 제거할 수 있게 된다.