[백준] 17136 색종이 붙이기

---

10 * 10 격자판의 1을 모두 덮는 최소 색종이 개수를 구하는 문제이다.

 

단순 반복문 보다는 백트래킹 알고리즘을 사용하면 쉽게 해결할 수 있다.

 

1. 색종이 사이즈 배열 S에 지금까지 사용한 색종이의 개수를 저장한다.

2. 재귀 함수를 사용한다. 열 번호를 하나씩 증가시키고 열 번호가 10일 경우 행 번호를 하나 증가시키고 다시 열번호를 0으로 초기화한다.

3. 열번호가 10일 경우 색종이의 총 개수를 반환하며, 가장 작은 경우를 출력한다.

 

색종이 사이즈가 s * s라고 할때 s에 0 - 4를 대입하여 반복한다. 만일 해당 색종이를 5장 미만 사용했다면 해당 구간의 배열을 완전탐색하여 모든 값이 1인 경우 색종이로 덮는다. 이는 1을 0으로 치환하는 것으로 대신한다. 덮은 후 열 번호를 s+1 증가시키고 재귀 호출한다.

 

Python

 

	from sys import stdin
	readline = stdin.readline
	_map = [list(map(int, readline().split())) for _ in range(10)]
	def solve(row, col, size):
	global ans
	if row == 10:
	ans = min(ans, sum(size))
	return
	if col == 10:
	solve(row+1, 0, size)
	return
	if _map[row][col] == 0:
	solve(row, col+1, size)
	return
	for s in range(4, -1, -1):
	# 해당 사이즈 종이를 5개 썼을 경우
	if size[s] == 5: continue
	if row+s < 10 and col+s < 10:
	flag = True
	for i in range(row, row+s+1):
	for j in range(col, col+s+1):
	# 적어도 하나 이상 0이면 s * s 크기의
	# 색종이로 덮을 수 없음
	if _map[i][j] == 0:
	flag = False
	break
	if not flag : break
	# s * s 색종이로 덮는 것이 가능한 경우
	if flag:
	for i in range(row, row+s+1):
	for j in range(col, col+s+1):
	_map[i][j] = 0
	size[s] += 1
	solve(row, col+s+1, size)
	size[s] -= 1
	for i in range(row, row+s+1):
	for j in range(col, col+s+1):
	_map[i][j] = 1
	li = [0] * 6
	ans = 26
	solve(0, 0, li)
	print(ans if ans != 26 else -1)

view raw BOJ17136 hosted with ❤ by GitHub