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

안녕하세요? 닉네임간편입니다.

이번 시간에는 색종이 붙이기 문제를 풀어보겠습니다.

[문제 링크]

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

17136번: 색종이 붙이기

1. 접근 방식

1x1부터 5x5까지의 색종이로 모든 1을 덮는데 필요한 색종이의 최소 개수를 찾아야 합니다. 따라서 BFS 방식으로 접근할 수 있지만, 매번 동작을 반복할 때마다 배열의 상태를 깊은 복사 하여 전달해야 한다는 점 때문에 시간적, 공간적으로 효율적이지 않습니다. 물론 다른 방식도 있을 수 있겠지만, 저는 그보다 쉽게 풀이를 작성할 수 있는 DFS 방식으로 접근했습니다.

먼저 0,0 좌표부터 시작해서 1인 지점을 찾습니다. 
1인 지점을 찾았다면 해당 부분과 인접한 1이 있는 곳을 덮을 수 있는 색종이의 최대 크기를 구합니다. 그리고 최대 크기부터 1까지 색종이를 덮은 다음 dfs 함수를 다시 호출합니다. 이를 반복하면서 모든 칸이 0으로 채워졌다면 이때의 횟수를 반환하고, 만일 모두 0으로 채우지 못했거나 색종이가 부족해졌다면 -1을 반환하도록 합니다. 그리고 이를 결과 집합에 추가합니다.

이후 최종적으로 dfs 함수가 종료되었다면 결과 집합에서 최솟값을 출력합니다.

2. 전체 코드

import sys

input = sys.stdin.readline
board = [list(map(int, input().split())) for _ in range(10)]
papers = [0, 5, 5, 5, 5, 5]
result = set()


# 색종이 최대 길이 구하는 함수
def find_length(y, x):
    length = 1
    for l in range(2, min(10 - y, 10 - x, 5) + 1):
        for i in range(y, y + l):
            for j in range(x, x + l):
                if board[i][j] == 0:
                    return length
        length += 1
    return length


# 색종이 덮는 함수
def cover(y, x, length):
    for i in range(y, y + length):
        for j in range(x, x + length):
            board[i][j] = 0


# 색종이 치우는 함수
def uncover(y, x, length):
    for i in range(y, y + length):
        for j in range(x, x + length):
            board[i][j] = 1


def dfs(cnt):
    for i in range(0, 10):
        for j in range(0, 10):
            if board[i][j] == 1:
                length = find_length(i, j)
                for l in range(length, 0, -1):
                    if papers[l]:
                        cover(i, j, l)
                        papers[l] -= 1
                        result.add(dfs(cnt + 1))
                        uncover(i, j, l)
                        papers[l] += 1
                if result:
                    return min(result)
                else:
                    return -1
    return cnt


result.add(dfs(0))
if -1 in result:
    result.remove(-1)
print(min(result) if result else -1)

 

이제부터 차근차근 알아보겠습니다.

3. 코드 분석

1) 입력받기 및 배열&집합 생성

import sys

input = sys.stdin.readline
board = [list(map(int, input().split())) for _ in range(10)]
papers = [0, 5, 5, 5, 5, 5]
result = set()

 

10x10 배열을 board로 입력받습니다.

각 인덱스 별로 남아있는 색종이 개수를 나타내는 papers 배열과, dfs 메서드에서 반환하는 결과를 추가할 result 집합을 생성합니다. 이때 resutl를 집합으로 사용한 이유는 중복된 값을 미리 막아주고, 값을 제거할 때 최악의 경우가 아니라면 평균적으로 시간 복잡도가 O(1)이기 때문입니다.

2) 색종이 최대 길이 구하는 함수 정의

# 색종이 최대 길이 구하는 함수
def find_length(y, x):
    length = 1
    for l in range(2, min(10 - y, 10 - x, 5) + 1):
        for i in range(y, y + l):
            for j in range(x, x + l):
                if board[i][j] == 0:
                    return length
        length += 1
    return length

 

파라미터로 전달받은 x, y 좌표를 기준으로 덮을 수 있는 색종이의 최대 길이를 구합니다. 이때 x, y는 사각형의 왼쪽 위가 되며, 이를 기준으로 오른쪽, 아래쪽으로 확장되어 사각형의 최대 길이가 정해집니다.

우선 이 함수가 호출될 때는 board에서 해당 좌표의 값이 1인 경우이므로, 무조건 길이는 1부터 시작입니다. 이후 2부터 최대 길이를 검증하며, 최대 5까지 검증해야 하지만 x, y의 값에 5를 더할 때 배열 범위를 벗어나는 경우를 방지하기 위해 min 함수를 사용했습니다.

이후 이중 반복문을 사용하여 만일 사각형 범위 내의 좌표 중 0이 하나라도 있다면 이전까지의 최대 길이를 반환합니다. 만일 모두 1이라면 최대 길이에 1을 추가하고, 다음 길이에 대해서 동작을 반복합니다. 이후 길이를 반환합니다.

3) 색종이 덮는 함수, 지우는 함수 정의

# 색종이 덮는 함수
def cover(y, x, length):
    for i in range(y, y + length):
        for j in range(x, x + length):
            board[i][j] = 0


# 색종이 지우는 함수
def uncover(y, x, length):
    for i in range(y, y + length):
        for j in range(x, x + length):
            board[i][j] = 1

 

입력받은 좌표와 사각형의 길이를 이용해 해당 사각형 부분을 색종이로 덮거나 지웁니다.

두 동작은 0과 1의 값을 제외하곤 동일합니다.

4) dfs 함수 정의

def dfs(cnt):
    for i in range(0, 10):
        for j in range(0, 10):
            if board[i][j] == 1:
                length = find_length(i, j)
                for l in range(length, 0, -1):
                    if papers[l]:
                        cover(i, j, l)
                        papers[l] -= 1
                        result.add(dfs(cnt + 1))
                        uncover(i, j, l)
                        papers[l] += 1
                if result:
                    return min(result)
                else:
                    return -1
    return cnt

 

a) 먼저 횟수(cnt)를 파라미터로 전달받습니다.

b) 이후 이중 반복문을 통해 board에서 해당 좌표 값이 1이라면, 다음 동작을 수행합니다. 만일 그렇지 않고 모두 0으로 채워졌다면, 현재 cnt를 반환합니다.

c) 앞서 정의한 find_length() 메서드를 이용해 최대 길이를 찾습니다. 이후 최대 길이부터 1까지 반복하여 각 길이만큼의 색종이를 덮고, dfs() 메서드를 호출합니다. 이후 이 dfs() 메서드가 계속적으로 호출되어 board의 모든 칸을 0으로 채웠다면 cnt를 반환할 것이고, 그렇지 않다면 -1을 반환할 것입니다. 이를 결과 집합 result에 추가합니다.

dfs가 종료된 이후에는 다음 dfs를 호출하기 이전에 색종이를 다시 지우고 색종이 개수로 원상복귀시킵니다. 이는 하나의 배열을 공유하며 사용하기 때문에 추가한 부분입니다.

d) 모든 색종이의 최대 길이에 대해서 동작이 완료되면 결과 집합의 최솟값을 반환합니다. 만일 결과 집합에 요소가 없다면 board의 모든 칸을 0으로 채우지 못했다는 것이므로, -1을 반환합니다.

5) 결과 출력

result.add(dfs(0))
if -1 in result:
    result.remove(-1)
print(min(result) if result else -1)

 

먼저 결과 집합에 dfs(0)을 추가합니다.

이후 결과 집합에 -1이 있다면 이를 제거해줍니다.

만약 여전히 결과 집합에 요소가 있다면 최솟값을 출력하고, 요소가 없다면 -1을 출력합니다.

4. 마무리

저에게는 다소 어려운 문제였기에 해결하는 데 시간이 많이 소요된 문제입니다. 또한 온전히 혼자 했다기보단 다른 분들의 도움을 좀 받기도 했습니다. 그래도 이번 문제를 풀면서 확실히 부족했던 DFS에 대한 지식을 쌓았기에, 뜻깊은 시간이었습니다.