백준[17136] 색종이 붙이기 (Python3)

최대한 단순하고 모듈화를 해야 쉽게 푸는 문제
똑똑하게 풀려다 인덱스 안 맞아서 2번 정도 틀렸다.

어떤 종이부터 붙여야 할까?

어떤 종이부터 붙이냐에 따라 풀이 방식이 살짝 달라진다.
각자 취향에 맞춰서 하면 된다.
이 글에선 큰 종이부터 붙여나갔다.

큰 종이부터

한번 최적의 해가 나오면 이후 탐색에서 해당 탐색을 넘어선다면 그냥 탐색을 중단하면 된다.

작은 종이부터

색종이가 부족한 경우를 제외하고, 중간 크기의 색종이를 붙일 수 없을 때, 그거보다 큰 색종이는 붙일 수 없는 게 자명하다. 다음 위치부터 탐색을 진행하면 된다.

모듈화 하기

메소드 하나에 모두 작성하기엔 많은 indent가 발생했기에, 코드 보는 부담을 줄이기 위해 모듈화를 했다.

문제에서 요구하는 기능들을 모아서 다음 기능들을 모듈화했다.

1. 범위 체크 (check)
2. 색종이 붙이기 (fill)
3. 색종이 떼기 (restore)
4. 색종이가 모두 붙여졌는지 보기 (fillCheck)

각 모듈화된 코드는 단순히 해당 위치부터 이중 포문을 돌려 O(M^2)로 탐색했다. (M = 색종이의 한 변 길이)

시간 복잡도 분석

값이 모두 1이라고 가정한다. 일단은 색종이 제한은 고려하지 않는다.
처음 10 * 10 종이의 값들이 모두 0인지 확인(fillCheck 호출, O(10 * 10))
10 * 10 종이를 처음부터 탐색해 1이 있는 영역을 찾는다.(O(10 * 10))
1인 칸이 있다면, 모든 색종이를 대입해 본다.

 

대입하는 과정에서 크기 검증(check), 색종이 붙이기(fill), 색종이 떼기(restore)로 3개의 메소드 호출이 발생하고, 모든 색종이를 대본다 할 때 각 메소드당 O(1 * 1) + O(2 * 2) + O(3 * 3) + O(4 * 4) + O(5 * 5)로 약 50번의 탐색이 발생한다.

 

종합하면 (10 * 10) * (10 * 10) * (50 * 3 * 5 + 50)으로 8,000,000 번의 탐색이 발생한다.
(전체 dfs 조회) * (1 탐색) * (((fill + restore + check) * 색종이 5종류) + fillCheck)
여기서 색종이 제한까지 고려하면 더 빠르게 결과가 나오는 것을 알 수 있다.

 

코드

dir = [[1, 0], [0, 1], [1, 1]]
sizes = [0, 0, 0, 0, 0, 0]
visit = [[False for _ in range(10)] for _ in range(10)]
N = 10
ans = float("inf")
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

def main():
    dfs(0)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

def dfs(count):
    global ans
    if count >= ans:
        return
    if fillCheck():
        ans = min(ans, sum(sizes))
        return

    for y in range(N):
        for x in range(N):
            if not board[y][x]:
                continue
            for s in range(4, -1, -1):
                if sizes[s + 1] >= 5:
                    continue
                if y + s >= N or x + s >= N:
                    continue
                if not check(y, x, s):
                    continue
                fill(y, x, s)
                dfs(count + 1)
                restore(y, x, s)
            return

def fillCheck():
    for y in range(N):
        for x in range(N):
            if board[y][x]:
                return False
    return True

def check(Y, X, s):
    for y in range(Y, Y + s + 1):
        for x in range(X, X + s + 1):
            if not board[y][x]:
                return False
    return True

def fill(Y, X, s):
    for y in range(Y, Y + s + 1):
        for x in range(X, X + s + 1):
            board[y][x] = 0
    sizes[s + 1] += 1

def restore(Y, X, s):
    for y in range(Y, Y + s + 1):
        for x in range(X, X + s + 1):
            board[y][x] = 1
    sizes[s + 1] -= 1




if __name__ == "__main__":
    main()