17163. 색종이 붙이기

문제 링크

17163. 색종이 붙이기

문제 코드

def paper(idx,count):
    global min_count,result

    if count >= min_count:
        return
    #print_paper()

    if idx == len(one_list):
        min_count = min(min_count,count)
        return

    i, j = one_list[idx]

    if graph[i][j] == 0:
        paper(idx+1,count)
        return

    for size in range(5,0,-1):
        checker = True
        if i+size < 11 and j+size <11:
            for x in range(i,i+size):
                for y in range(j,j+size):
                    if graph[x][y] == 0:
                        checker = False
            if checker and paper_list[size-1]>0:
                for x in range(i, i + size):
                    for y in range(j, j + size):
                        graph[x][y] = 0
                paper_list[size - 1] -= 1
                #print_paper()
                paper(idx+1,count+1)
                for x in range(i, i + size):
                    for y in range(j, j + size):
                        graph[x][y] = 1
                paper_list[size - 1] += 1


graph = [[0 for row in range(10)]for col in range(10)]
one_list = []
for i in range(10):
    num_list = list(map(int,input().split()))

    for j in range(10):
        graph[i][j] = num_list[j]
        if num_list[j] == 1:
            one_list.append([i,j])


paper_list = [5,5,5,5,5]
count = 0
result = 0
min_count = 26

paper(0,0)


if min_count == 26:
    print(-1)
else:
    print(min_count)

문제 풀이

• 처음 시도
  • 5*5짜리 종이를 붙이고 붙인 부분을 0으로 만들어서 몇개 붙이는지 확인해봄
  • 5개가 넘는 종이를 붙이면 -1 출력
• 시도 2
  • 예시 1번을 넣었을때 답이 4가 나와야 하나, 5*5부터 붙이므로 -1을 리턴하는것을 확인
  • 55부터 붙여보고 안되면 44 3*3 순으로 내려가면서 붙여보도록 함
  • 가장 min을 찾아야 하므로 모든 케이스를 다해보고 가장 적은 종이를 붙이는 걸 출력하도록 함
• 시도 3
  • 예시 2번을 넣었을때 답이 5가 나와야 하나, 지금 기준으로는 5*5를 만족하는 답이 그래프 상에 있으면 바로 붙여버림
  • 전부 다 붙이도록 해봐야함
• 시도 4
  • 백트래킹으로 전환함
  • 입력받을때 1이 위치하는 위치를 기록하도록 함
  • 백트래킹을 돌때 인덱스를 통해서 돌도록 함

추가 예시

예시 1번
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
answer : 4
예시 2번
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
answer : 5