[코딩으로 풀어보기] 문제적 남자 195화 ROUND 5, 규칙에 맞게 화살표를 색칠하라.

문제

2019년 초에 신년을 맞아 싱가포르 국립대학교(NUS) 천재들과의 문제 배틀이 있었다.

그 중 하나로, 빨간 화살표가 가리키는 방향에는 빨간 화살표가 2개만, 회색 화살표가 가리키는 방향에는 빨간 화살표가 2개가 아니도록 화살표를 색칠하는 문제가 있었다.

규칙을 만족하는 포인트를 파악해서 논리적으로 연결해나가는 것이 맞지만, 우리는 컴퓨터가 있다.

무식하게 모든 경우를 전부 확인해보자. 정말 답이 하나일까?

세로 4행, 가로 5열 총 전체 20개의 칸을 모두 색칠해보는 경우는, 각 칸을 색칠한다/하지않는다 2가지의 선택이 20개 칸마다 있는 것이므로

\(O(2^{20})\)이다. 색칠 후에는 각 화살표들이 모두 규칙을 만족하는 지 확인해야하므로 연산이 조금 더 붙지만, 그래도 3천만번 이하로 계산된다.

이 정도면 1초 내에 답이 나오는 정도이니, 코딩해서 답을 구하고 확인하는 건 어려워보이지 않는다.

코드

결과는,

 RED GRAY  RED  RED GRAY 

GRAY GRAY GRAY  RED  RED 

GRAY GRAY  RED  RED  RED 

GRAY  RED  RED  RED GRAY

문제적 남자에서는 직관으로 화살표 하나를 색칠하고, 스도쿠를 해결하듯 규칙에 맞도록 색칠해나갔다.

(이 문제는 나중에 파이썬으로 다시 구현해서, 영상을 추가할 예정) 시간이 없어서 계획 취소.