[코딩으로 풀어보기] 문제적 남자 66화, 모든 구역을 관찰하려면 몇 개의 초소가 필요할까?

문제적 남자 66화, 모든 구역을 관찰하려면 몇 개의 초소가 필요할까?

문제 출처: 문제적 남자 66화 (2016.06.19) - 타일러 신의 한 수,발상의 전환!

우연히 유튜브에서 위 그림과 같은 문제를 봤다.

가로, 세로, 대각선 방향으로 관찰 가능한 감시초소가 있을 때, 모든 구역을 관찰하려면 최소 몇 개의 초소가 필요한지 묻는 문제이다. 구역의 크기는 가로와 세로의 길이가 모두 7인 정사각형이다. 결론부터 말하자면, 정답은 최소 4개의 초소가 필요하다.

그런데 4개의 초소를 설치하는 방법이 하나가 아니다. 문제적 남자에서는 아래와 같은 배치를 타일러가 제시했고 정답으로 인정되었다.

타일러의 정답

하지만 제작진이 준비한 답은 이랬다.

제작진의 정답

여기서 의문이 생겼다.

그럼 위 두가지를 제외하고 몇 개의 정답이 더 있을까?
그래서 코딩으로 풀어보자는 생각이 들었다.

총 86개의 경우의 수가 있었고, 정사각형이다보니 상하좌우 대칭으로 같은 모양이 꽤 나왔다. 회전해도 서로 같지 않은 모양은 30개보다 적을 것 같다.

아래는 시뮬레이션을 위해 파이썬으로 작성한 스크립트이다.

	# from https://mcsp.wartburg.edu/zelle/python/graphics.py
	from graphics import *
	from time import sleep
	N = width = height = 0
	grid = []
	win = GraphWin(width=400, height=400)
	class Cell:
	rect = None
	window = None
	is_tower = False
	is_hide = True
	x, y = 0, 0
	WHITE_COLOR = color_rgb(255, 255, 255)
	TOWER_COLOR = color_rgb(64, 64, 255)
	BLUE_COLOR = color_rgb(192, 192, 255)
	def __init__(self, x, y):
	self.x = x
	self.y = y
	self.rect = Rectangle(Point(x, y), Point(x+1, y+1))
	self.rect.setFill(self.WHITE_COLOR)
	def setWindow(self, window):
	self.window = window
	def draw(self, window=None):
	self.rect.draw(window if window else self.window)
	def clear(self):
	self.is_tower = False
	self.is_hide = True
	self.colorSync()
	def colorSync(self):
	color = self.WHITE_COLOR
	if self.is_tower:
	color = self.TOWER_COLOR
	elif not self.is_hide:
	color = self.BLUE_COLOR
	self.rect.setFill(color)
	# 8방향의 시야 설정
	def buildTower(grid, colored, cell):
	global width, height
	x, y = cell.x, cell.y
	delta = [
	(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)
	]
	lines = []
	for (dy, dx) in delta:
	cx, cy = x - 1, y - 1
	start_point = cell.rect.getCenter()
	end_point = start_point
	while 0 <= cx < width-2 and 0 <= cy < height-2:
	if (cy, cx) not in colored:
	colored.append((cy, cx))
	grid[cy][cx].is_hide = False
	end_point = grid[cy][cx].rect.getCenter()
	cx += dx
	cy += dy
	if start_point != end_point:
	lines.append(Line(start_point, end_point))
	return lines
	# 초소를 k개 설치하는 경우를 dfs
	def dfs(cur_point, points, k):
	if len(points) >= k:
	towers = [grid[p // N][p % N] for p in points]
	colored = []
	lines = []
	for tower in towers:
	lines += buildTower(grid, colored, tower)
	if N * N == len(colored):
	for t in towers:
	t.is_tower = True
	for c in colored:
	grid[c[0]][c[1]].colorSync()
	for l in lines:
	l.setFill(color_rgb(128, 128, 255))
	l.setArrow("last")
	l.draw(win)
	sleep(1)
	for c in colored:
	grid[c[0]][c[1]].clear()
	for l in lines:
	l.undraw()
	return 1
	return 0
	answer_count = 0
	for p in range(cur_point + 1, N * N):
	answer_count += dfs(p, points + [p], k)
	return answer_count
	# n*n 크기를 k개의 초소로 푸는 법
	def solve(n, k):
	global N, width, height, grid, win
	N = n
	width = height = N + 2
	win.setCoords(0, 0, width, height)
	grid = []
	for y in range(1, height-1):
	row = []
	for x in range(1, width-1):
	cell = Cell(x, y)
	cell.setWindow(win)
	cell.draw()
	row.append(cell)
	grid.append(row)
	return dfs(0, [], k)
	if __name__ == "__main__":
	answers = solve(7, 4)
	print(answers)
	# 끝났음을 알리는 노란 색칠
	for row in grid:
	for cell in row:
	cell.rect.setFill(color_rgb(255, 255, 128))
	win.getMouse() # pause windows

view raw The-Brainiacs-E66.py hosted with ❤ by GitHub

그래픽 라이브러리는 https://mcsp.wartburg.edu/zelle/python/graphics.py에서 제공되는 것을 사용하였는데, 꽤 괜찮았다.

7*7 크기 말고도 다른 크기에서의 초소 배치도 궁금해서 함수를 N*N 크기의 구역에서 k개의 초소가 있을 때 모든 경우의 수를 구하도록 작성했다.