[BOJ 22359] 흔한 타일 색칠 문제

https://www.acmicpc.net/problem/22359

22359번: 흔한 타일 색칠 문제

 

[#BOJ_14601] 샤워실 바닥 깔기 (Large) 와 상당히 유사한 문제로, 정사각형 타일 하나를 뺀 2^k × 2^k 정사각형 판을 L-트로미노로 채우는 문제에서 3개 이하의 색으로 모든 L-트로미노를 구별되게 칠해야 한다는 조건이 추가된 문제입니다. L-트로미노를 배치하는 방법 자체는 14601번 문제와 같기 때문에 이 글에서는 생략했습니다.

 

3개 이하의 색으로 모든 L-트로미노를 구별되게 칠하는 방법은 다음과 같습니다. 2ⁿ × 2ⁿ (n ≥ 2) 부분 문제에 대해 중앙에 배치된 L-트로미노의 방향이 확정될 때마다 첫 번째 색으로 칠하고, 2 × 2 부분 문제에 도달했을 때 두 번째 또는 세 번째 색으로 칠하면 조건을 만족하는 색상 배치를 얻을 수 있습니다. 이때 두 번째 또는 세 번째 색은 한 칸의 크기가 2 × 2 인 격자판과 같이 칠하되 이미 색칠되거나 뚫린 부분은 제외하며 칠한다고 생각하면 쉽게 칠할 수 있습니다. 

 

L-트로미노를 배치하고 색칠하는 과정