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

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

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

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

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

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

타일러의 정답

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

제작진의 정답

여기서 의문이 생겼다.

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

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

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

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

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