[알고리즘] 분할정복 - 백준 2630번 색종이 만들기

import sys
N = int(sys.stdin.readline())
papers = [list(map(int, input().split())) for _ in range(N)]
white_paper, blue_paper = 0, 0

def solution(x, y, n):
    global white_paper, blue_paper
    color = papers[x][y]

    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != papers[i][j]:
                solution(x, y, n//2)
                solution(x, y+n//2, n//2)
                solution(x+n//2, y, n//2)
                solution(x+n//2, y+n//2, n//2)
                return
    if color == 0:
        white_paper += 1
    else:
        blue_paper += 1


solution(0, 0, N)
print(white_paper)
print(blue_paper)

풀이과정

1. 색종이를 2차원 배열로 받는다. input() 대신 sys.stdin.readline() 을 사용하면 효율성이 더 좋다.
2. 구해야 할 하얀색, 파란색 색종이는 global로 받아야한다.
3. 첫번째 위치의 색종이 색깔을 color에 담는다.
4. 나눠진 부분의 이중 for문을 돌면서 하나라도 color와 같지 않다면 재귀를 이용하여 사분면으로 나눈다.
5. 모든 색이 같은 경우, 종이의 개수를 구한다.

다른 사람 풀이

import sys
N = int(sys.stdin.readline())
papers = [list(map(int, input().split())) for _ in range(N)]
white_paper, blue_paper = 0, 0

def checkPaper(x, y, n):
    global white_paper, blue_paper
    color = papers[x][y]    # 첫 번째 위치의 숫자
    flag = True             # 반복문 빠져나오기 위한 변수

    for i in range(x, x+n):
        if not flag:    # 반복문 아예 빠져나와야 하니까 한번 더 break
            break
        for j in range(y, y+n):
            if color != papers[i][j]:   # 숫자가 하나라도 다르면 사분면 나눠야 함
                flag = False
                checkPaper(x, y, n//2)
                checkPaper(x, y+n//2, n//2)
                checkPaper(x+n//2, y, n//2)
                checkPaper(x+n//2, y+n//2, n//2)
                break
    
    if flag:    # 모든 숫자가 다 똑같은 경우
        if color == 0:
            white_paper += 1
        else:
            blue_paper += 1


checkPaper(0, 0, N)
print(white_paper)
print(blue_paper)

반복문을 빠져나올 때 return이 아닌 break 를 해주는 방법도 있다.
시간이 4ms 정도 빠르다. flag 변수를 사용하여 적용되어야 할 부분을 잘 나눠준 방법이다.