7월의 퍼즐에 참여해주신 모든 분들께 감사드립니다!
7월의 퍼즐에 참여해주신 분 중 정답과 함께 좋은 풀이를 보내주신
전형록님께 문화상품권을 전달드릴 예정입니다.
먼저 격자를 체크무늬로, 흰색과 회색을 사용하여 색칠해 보자. 편의상 흰색 칸은 색칠되지 않은 칸이라고 하겠다. 그러면 격자에 놓인 도미노는 항상 하나의 색칠된 칸을 포함한다.
이제 모든 회색 칸을 다른 색으로 적절히 색칠할 것이다. 물론 우리의 목표는 격자칸을 색칠하는 것이 아니라 도미노를 색칠하는 것이다. 도미노는 항상 색칠된 칸을 정확히 하나 포함하므로, 도미노가 포함하는 칸의 색깔로 도미노를 칠하는 방법을 생각할 수 있다.
이 방법이 성립하기 위해서는 같은 색깔끼리 멀리 떨어져 있어야 한다. 빨간색을 아래와 같은 규칙으로 색칠한다면, 빨간색 칸을 포함하는 어떤 두 도미노도 인접할 수 없게 된다.
나머지 칸들도 같은 규칙으로 색칠해 주면, 총 네 가지 색으로 모든 회색 칸을 색칠할 수 있다.
도미노가 포함하는 칸의 색깔로 도미노를 색칠하면 같은 색깔의 도미노끼리는 인접할 수 없다. 따라서 어떤 도미노 배치가 주어지든, 모든 도미노를 네 가지 색으로 색칠하는 것이 가능하다.
예를 들어, 문제에서 주어진 도미노 배치는 다음과 같이 색칠할 수 있다.
의도한 답안 이외에도, 그래프의 특성을 활용한 다양한 풀이가 존재한다. 7월의 정답자는 필자가 예상하지 못한 간단한 풀이를 찾아낸 전형록님으로 선정하였다.
다음은 7월의 정답자로 선정된 전형록님의 해설입니다.
우선 도미노를 색칠하는 순서를 정하자. 어떤 도미노를 칠하기 위해선 해당 도미노의 왼쪽과 위쪽에 위치한 도미노들을 먼저 칠해야 한다고 하자.
도미노를 정점으로,먼저 칠해야 되는 조건을 간선으로 하여 그래프로 표현하면 out-degree가 최대 3인 사이클이 없는 방향 그래프로 표현할 수 있다. (왼쪽,위쪽 길이의 합이 항상 3이므로 왼쪽과 위쪽에 최대 3개의 도미노가 인접할 수 있다)
해당 그래프에서 위상정렬을 통해 색칠할 순서를 구하고 각 도미노를 색칠 할 때 왼쪽, 위쪽에 인접한 도미노의 색과 (최대 3개) 다른 색을 칠하면 된다. 이미 칠해진 색 최대 3개 + 새롭게 칠한 색 1개 = 4가지 색으로 모든 도미노를 칠할 수 있다.
