[ BOJ / Python ] 17136번 색종이 붙이기

황승환·2022년 8월 9일
0

Python

목록 보기
428/498


이번 문제는 백트레킹을 통해 해결하였다. 조금 복잡한 백트레킹이었는데, 우선 함수의 인자로 y, x를 받는다. 이는 좌표를 의미하고, 좌표를 오른쪽으로 이동시키면서 끝에 도달하면 아래로 한칸 내리는 식으로 진행하였다. 현재 좌표 값이 1이라면 1~5에 해당하는 색종이 크기만큼을 확인하고, 사이즈가 맞는 경우에만 해당 좌표들을 0으로 바꿔주고 재귀호출하고, 다시 값을 원래대로 돌려놓는 방식으로 진행하였고, 이 과정에서 현재 선택한 색종이의 총 갯수가 5개가 넘지 않도록 하였다. 재귀호출을 할 때에는 선택한 색종이의 크기+1만큼을 x좌표에 더하여 진행해주고, 현재 좌표값이 0일 경우에는 x좌표를 1만 더 크게하여 다음 재귀호출을 진행하였다. 이 과정에서 y가 10 이상이 되면 결과 변수의 최솟값을 구하도록 하였고, 최종 결과 변수가 1e9일 경우, -1로 갱신해주었다.

Code

grid = [list(map(int, input().split())) for _ in range(10)]
cnts = [0 for _ in range(5)]
answer = 1e9
def chk(y, x, sz):
    for i in range(y, y+sz+1):
        for j in range(x, x+sz+1):
            if grid[i][j] == 0:
                return False
    return True
def find_min(y, x):
    global answer
    if y >= 10:
        answer = min(answer, sum(cnts))
        return
    if x >= 10:
        find_min(y+1, 0)
        return
    if grid[y][x] == 1:
        for sz in range(5):
            if cnts[sz] >= 5:
                continue
            if not (0 <= y + sz < 10 and 0 <= x + sz < 10):
                continue
            if chk(y, x, sz):
                for i in range(y, y+sz+1):
                    for j in range(x, x+sz+1):
                        grid[i][j] = 0
                cnts[sz] += 1
                find_min(y, x+sz+1)
                cnts[sz] -= 1
                for i in range(y, y+sz+1):
                    for j in range(x, x+sz+1):
                        grid[i][j] = 1
    else:
        find_min(y, x+1)
find_min(0, 0)
if answer == 1e9:
    answer = -1
print(answer)

profile
꾸준함을 꿈꾸는 SW 전공 학부생의 개발 일기

0개의 댓글