백준 2630 색종이 만들기 파이썬

2630번: 색종이 만들기

Baekjoon Online Judge스타트링크 (Startlink)

2630번 : 색종이 만들기
알고리즘 : 재귀, 분할정복

정답 코드

코드1 (재귀)

import sys
input = sys.stdin.readline

w = 0
b = 0
arr = []

def check(k:int, r: int, c: int) -> None:
    global w,b 
    for i in range(r, r + k):
        for j in range(c, c + k):
            if arr[i][j] != arr[r][c]:
                check(k//2, r, c)
                check(k//2, r + k//2, c)
                check(k//2, r, c + k//2)
                check(k//2, r + k//2, c + k//2)
                return

    if arr[r][c] == 1:
        b += 1
    else:
        w += 1

n = int(input())
arr = [None] * n
for i in range(n):
    arr[i] = list(map(int, input().split()))
check(n, 0, 0)
print(w)
print(b)

코드2 (반복문, 큐)

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
arr = [None] * n
for i in range(n):
    arr[i] = list(map(int, input().split()))
w, b = 0, 0
q = deque([[n, 0, 0]])

while q:
    k, r, c = q.pop()

    flag = 0
    for i in range(r, r + k):
        for j in range(c, c + k):
            if arr[i][j] != arr[r][c]:
                q.appendleft([k//2, r, c])
                q.appendleft([k//2, r + k//2, c])
                q.appendleft([k//2, r, c + k//2])
                q.appendleft([k//2, r + k//2, c + k//2])
                flag = 1
                break
        if flag == 1: break

    if flag == 0:
        if arr[r][c] == 1:
            b += 1
        else:
            w += 1   

print(w)
print(b)

해설

해당 문제는 분할정복을 활용한 재귀를 사용하면 어렵지 않게 풀 수 있습니다.

함수 check에 크기(k), 시작 행, 열(r , c)을 인자로 확인 할 사각형을 알려줍니다.
사각형 내부 요소 전체와 사각형 내부 (0,0) 위치의 정보를 순차적으로 비교하며
모두 동일한 색으로 칠해졌는지 확인하고, 칠한 색이 다른 순간 비교를 중지합니다.

사각형 내부가 모두 같은 색으로 칠해져 있지 않다면,
사각형을 다시 사분할 하여 검사합니다.

만약 크기가 k, 시작 위치가 (r , c)이라면 분할된 사각형은 각
크기 k // 2, 시작위치 (r , c)
크기 k // 2, 시작위치 (r + k //2 , c)
크기 k // 2, 시작위치 (r , c + k //2)
크기 k // 2, 시작위치 (r + k //2 , c + k //2) 일 것입니다.

Review

맨 처음 짠 코드의 시간은 88ms였는데, 다른 사람은 40 ~ 60ms 안에 풀었습니다.

처음에는 재귀가 아닌 deque를 사용한 큐 구조로 문제를 풀었고,
1. k = 1 (사각형의 크기가 1 )인 경우
2. 사각형 내부가 전부 파란색인 경우
3. 사각형 내부가 전부 하얀색인 경우,
위 3가지로 종료 조건을 정해 풀었습니다.

생각 1

1번 종료조건(k == 1)을 추가적으로 확인하지 않더라도 아래 반복문에서 정상적으로 종료 되므로 굳이 검사를 할 필요는 없었습니다.

또, 사각형을 한번 나눌 때 마다 확인 해야되는 경우가 4배가 되므로 최악의 경우를 위해 가장 크기가 작은 k = 1인 사각형만 먼저 확인하는것도 좋은 생각 같았습니다.

k == 1을 검사한다면 k == 1을 확인할 때 1번, k 가 하얀색인지, 파란색인지 1번
총 2번의 과정을 거칩니다.
k == 1을 검사를 하지 않는다면 반복문에서 2번(2차원) arr[i][j] 와 arr[r][c] 의 비교 1번 총 3번의 과정을 거치기에 큰 차이가 없습니다.

따라서 k = 1 인 경우를 따로 검사하는 부분을 삭제했습니다.

생각 2

전부 파란색/하얀색을 확인하기 위해 사각형 내부 전체를 확인하며 누적합을 구해
sum == k * k / sum == 0을 확인했습니다.

하지만 만약 색이 같다면 첫 인자와 나머지 전체는 항상 같을 것 이기 때문에
사각형 내부를 확인하며 첫 인자와 값이 달라지는 순간 반복문을 종료하면
전체를 확인하지 않아도 되므로 훨씬 빠르게 확인할 수 있습니다.

생각 1, 2를 적용하고 나니 84ms로 줄었습니다.
사실 생각 2에서 시간이 크게 차이가 나겠거니 했었는데 그렇지 않아 당황했습니다.

생각 3

설마 하는 생각에 큐 구조를 버리고 재귀로 바꾸어 풀어보았습니다.
파이썬은 내부에서 C로 돌아가는형태라 반복문에서도 오버헤드가 발생하는 것으로 알고 있습니다.
재귀로 구하니 역시나 104ms로 늘었습니다.
아무리 오버헤드가 발생한다 하더라도 반복문이 재귀보단 더 빨랐습니다.

생각 4

마지막으로 sys모듈을 불러와 입력을 받았습니다.

import sys
input = sys.stdin.readline

입력을 여러번 받는 형태의 문제가 아니라 굳이 적용하지 않았었습니다.
하지만 제출을 누른 순간 40ms가 눈앞에 보였습니다.
파이썬의 input는 상당히 느리다는걸 다시한번 깨닫게 되었습니다.