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
Author And Source
이 문제에 관하여(17163. 색종이 붙이기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@youngjin_kim2/17163.-색종이-붙이기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)