[문제적 남자] 가로, 세로, 대각선을 감시하는 초소가 있다. 모든 구역을 관찰하기 위해 최소 몇 개의 감시초소가 필요한가?

1. Question

2. Approach

7x7 칸에 모든 구역을 감시할 수 있도록 감시초소를 배치하는 문제.

문제 보자마자 딱 감시초소가 체스의 퀸과 비슷하다는 생각을 했고, 문제 자체도 8 Queen problem과 비슷하다는 생각을 했다.

8 Queen problem은 대표적인 NP-complete 문제로 유명하기 때문에 노가다밖에 답이 없다.

그래서 맘편하게 알고리즘이나 꼼수 찾을 생각 접고 그냥 배치해야겠다고 생각.

일단 조금이라도 편하게 노가다를 해보려고 몇 개의 퀸을 배치하면 최솟값에 근사하게 배치할 수 있을까 생각을 했다.

전체 49개의 칸 중에 퀸을 중간에 놓으면 가장 많을 공간을 커버할 수 있어서 25칸을 칠할 수 있고, 테두리에 배치하면 가장 적은 공간을 커버해서 19칸을 칠할 수 있다.

테두리에서 중앙으로 퀸이 이동할 때마다 추가적으로 2칸을 더 칠할 수 있게 된다.

또한, 하나의 퀸은 같은 행, 열 대각선을 공유하지 않는 다른 퀸과 부딪치며 약 5~6칸 정도 겹치게 된다.

3개의 퀸으로는 물리적으로 칸이 모자라서 못할 것 같고, 퀸을 4개까지 동원하니

$$19+21+23+25 - 20 = 68$$

$$19+21+23+25 - 24 = 64$$

로 충분히, 49개의 칸을 채울 수 있을 것 같아 4개로 만들 수 있도록 배치해봤다.

 

조금 시간이 걸려 답을 찾아 냈고 게스트 중에서도 타일러가 맞췄다. 내가 찾은 답과 타일러가 찾은 답은 동일했다.

타일러의 답

그런데, 반전은 제작진이 준비한 답은 이 답이 아니라는 것이다.

아래 그림이 제작진이 준비한 답이다.

제작진의 답

나는 당연히 퀸끼리 행, 열, 대각선을 공유하지 않아야 된다고 생각했는데, 공유하더라도 완벽하게 모든 칸을 커버해서 적지 않은 충격을 받았다.