[ 백준 17136 ] 색종이 붙이기 - Python

문제 보기

[ 사용한 알고리즘 ]

완전 탐색(브루트 포스)

 

[ 문제 접근 ]

처음에는 색종이의 크기가 큰 것부터 덮는 그리디 방식으로 구현하였습니다. 하지만 반례가 존재하였으며 모든 상황을 고려하지 않으면 정답을 도출할 수 없기 때문에 완전 탐색 방식으로 접근하였습니다.

 

[ 알고리즘 ]

1. 0의 위치를 찾습니다.

2. 해당 위치에 덮을 수 있는 색종이의 종류를 찾습니다.

3. 해당 위치에 색종이를 덮은 후 탐색을 계속 진행합니다.

4. 0이 존재하지 않으면 현재까지 사용한 색종이의 수와 현재까지 구한 색종이의 최솟값을 비교합니다.

 

[ 코드 ]

import sys
sys.setrecursionlimit(10 ** 9)


def check(array, row, col, depth):  # depth 크기의 색종이를 row, col 위치를 시작점으로 둘 수 있는지 확인
    # 범위 체크
    if row + depth > 10 or col + depth > 10:
        return False
    for i in range(row, row + depth):
        for j in range(col, col + depth):
            if array[i][j] == 0:
                return False
    return True


def dfs(array, remain_cnt, count):
    global result
    if result != -1 and sum(count) > result:
        return

    if remain_cnt == 0:  # 모든 1을 제거한 경우
        if result == -1:
            result = sum(count)
        else:
            result = min(result, sum(count))
        return

    # 색종이 삽입 위치 찾기
    row, col = -1, -1
    for i in range(10):
        for j in range(10):
            if array[i][j] == 1:
                row, col = i, j
                break
        if (row != -1 and col != -1) and array[row][col] == 1:
            break

    # row, col 위치에 대입 가능한 색종이 탐색
    for i in range(1, 6):
        if count[i - 1] == 5:  # 5개 이상 사용 불가능
            continue
        if check(array, row, col, i):  # 색종이 놓을 수 있는지 확인
            location = []
            for m in range(row, row + i):
                for n in range(col, col + i):
                    array[m][n] = 0
                    location.append((m, n))
            count[i - 1] += 1
            dfs(array, remain_cnt - i ** 2, count)
            count[i - 1] -= 1
            for x, y in location:  # 다시 1로 수정
                array[x][y] = 1


if __name__ == "__main__":
    maps = [list(map(int, input().split())) for _ in range(10)]

    # 1의 개수 파악
    one_num = 0
    for i in range(10):
        one_num += maps[i].count(1)

    result = -1

    # dfs 탐색
    dfs(maps, one_num, [0, 0, 0, 0, 0])
    print(result)