2414와 비슷한 문제처럼 보이지만, 같은 칸을 겹쳐서 색칠할수 있는지 없는지에 따라서 큰 차이가 있고, 전혀 다른 접근법이 필요하다. (공교롭게도 둘가 이분매칭이 정해이기는 하다.. 그래프 모델링 방법은 완전히 다르지만)
같은칸을 겹쳐서 색칠할 수 있는 2414는 각 행과 열을 노드로 하는 이분 그래프를 만드는 어느정도는 정형화된 모델링으로 해결할수 있다. 그러한 이분 그래프에서의 최소 버텍스 커버를 이분 매칭으로 구하면 된다
이 문제에서 N,M의 범위를 줄인 문제는 타일 놓기이다. 타일 놓기은 O(n*m*2^n)의 비트 스크롤링 DP로도 풀이가 가능하지만, 이 문제는 그렇게 풀면 시간 초과가 난다. 이분 매칭을 이용해서 O((n*m)*sqrt(m*n)) 에 풀수 있다.
문제를 이렇게 생각해보자. 색칠해야 하는 칸의 갯수가 m개인데 처음에는 각 칸마다 테두리가 다 쳐져있는 상태이다, 이중에서 인접한 두칸을 골라서 두칸 사이의 테두리를 지우는 것을 반복해서 n개의 테두리를 지운다. 그러면 이제 영역의 갯수는 m-n개이고, 한번에 각 영역을 색칠하는 식으로 m-n번 색칠해서 보드를 색칠하면 된다. 색칠 횟수를 최소화하려면, 영역의 갯수를 최소화해야 하고, 그러려면 테두리를 가장 많이 지우면 된다. 다만, 영역은 한 행이나 한 열에 연속되어야만 하는데, 이 조건을 만족시키려면 테두리를 지울때에 어떤 칸의 오른쪽/왼쪽 테두리와 위쪽/아래쪽 테두리를 동시에 지우는 경우가 생기지 않도록 하면 된다.
이렇게 풀어쓰고 나면 그래프로 어떻게 표현할지 보이기 시작한다. 각 테두리들을 노드로 만들고, 동시에 지워질수 없는 테두리들끼리 엣지로 연결해준 다음에, 노드들의 최대 독립집합을 구하면 된다. 테두리들을 세로방향 테두리들과 가로방향 테두리들로 나누면 엣지는 이 두그룹 사이에만 존재하므로, 이 그래프는 이분그래프이고, 그러므로 이분 매칭을 통해서 최대 독립집합을 구할 수 있다.
노드의 갯수는 O(n*m)이고, 각 노드마다 최대 degree는 4이므로, 엣지의 갯수도 O(n*m) 이다. 그래서 이분 매칭을 돌리는 총 시간 복잡도는 O((n*m)*sqrt(m*n)) 이 된다.