[백준] 2630번 (python 파이썬)

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

 

Divide and Conquer에 대한 문제이다.

1. 해당 종이가 일괄된 색이 아니면 4등분을 한다.

2. 4등분된 종이를 다시 검사한다.

1, 2를 일괄된 색일때까지 반복한다.

 

처음 푼방법

종이를 모든 수에 대해 검사하고 

4등분된 종이를 list로 만들어서 다시 재귀를 돌렸다.

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

blue_count = 0
white_count = 0


def makePaper(graph):
    if validPaper(graph):
        return

    left_top = list()
    right_top = list()
    left_bottom = list()
    right_bottom = list()

    for i in graph[:len(graph) // 2]:
        left_top.append(i[:len(i) // 2])
        right_top.append(i[len(i) // 2:])

    for i in graph[len(i) // 2:]:
        left_bottom.append(i[:len(i) // 2])
        right_bottom.append(i[len(i) // 2:])

    makePaper(left_top)
    makePaper(right_top)
    makePaper(left_bottom)
    makePaper(right_bottom)


def validPaper(graph: list):
    global white_count, blue_count
    white = True
    blue = True
    for i in graph:
        for j in i:
            if j != 0:
                blue = False
            else:
                white = False

    if white:
        white_count += 1
        return white
    if blue:
        blue_count += 1
        return blue


makePaper(graph)
print(blue_count)
print(white_count)

이렇게 되면 모든 좌표에 대해 검사하기때문에 반복횟수가 늘어나고 list를 4개를 더사용해야 하기 때문에 메모리도 비효율적이다.

 

2번째 방법

재귀를 돌릴때 list를 넘겨주는것이 아닌 좌표와 좌표의 개수에 대한 종보를 넘겨줬다.

또한 색종이를 검사할때 모든좌표를 검사하는 것이 아닌 첫좌표와 비교해가면서 다르면 바로 break를 걸어주었다.

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

blue_count = 0
white_count = 0


def makePaper(x, y, n):
    global blue_count, white_count

    check_color = graph[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if check_color != graph[i][j]:
                check_color = -1
                break

    if check_color == -1:
        n = n // 2
        makePaper(x, y, n)
        makePaper(x + n, y, n)
        makePaper(x, y + n, n)
        makePaper(x + n, y + n, n)
    elif check_color == 1:
        blue_count += 1
    elif check_color == 0:
        white_count += 1


makePaper(0, 0, n)
print(white_count)
print(blue_count)

 

코드도 줄어들고 조금 시간이 향상되었다.