[Hard] ColorfulBoard

먼저 다음 두가지 관찰을 찾을 필요가 있다. 1) 각 행/열에는 최대 한 번만 칠해야 한다. -> 어떤 행/열에 두 번 이상 색을 칠했다면 맨 마지막에 칠한 것만 유효하므로 한 번으로 줄일 수 있다. 2) 행/열 중 아무것도 칠하지 않아도 되는 행/열이 최소 1개 존재한다. -> 모든 행/열에 색을 하나씩 칠했다고 해보자. 이렇게 되면 맨 처음에 색칠한 행/열의 색은 다른 것들에 의해 모두 덮어씌워지게 된다. 따라서 맨 처음에 색칠한 그 행/열을 칠하지 않아도 된다. 이 두가지 관찰을 통해 모든 행을 하나씩 보면서 그 행을 아무것도 칠하지 않는 행이라고 결정한 후 그 상황에서 목표를 달성하는 최소 횟수를 찾을 것이다. (열을 칠하지 않는 경우는 판을 transpose 해놓고 똑같이 풀면 된다) 이제 내가 p번행에 아무것도 칠하지 않기로 했다고 해보자. 우선 C[p][1] ~ C[p][m] 은 전부 열을 통해 색칠되어야 한다. 따라서 j번열은 C[p][j]의 색으로 칠해져야 한다. 만약 p번행과 구성이 완전히 같은 행이 존재한다고 해보자. 그럼 그 행도 마찬가지로 아무것도 칠하지 않아도 된다. 따라서 p번행과는 구성이 다른 행들만 관심의 대상이 된다. 그런 행i에 대해서 만약 C[i][k] != C[p][k] 인 k가 존재한다면 i번행은 C[i][k]의 색으로 칠해져야 함을 알 수 있다. i번행을 칠해야 하는 색이 2가지 이상이라면 모순이므로 바로 다른 p로 넘어간다. 지금까지 각 행/열을 어떤 색으로 칠해야 하는지를 결정했다. 이제 이것들에 칠하는 순서를 적당히 정해서 입력으로 들어온 판을 실제로 만들 수 있는지 검사해야 한다. p번행과는 구성이 다른 행i에 대해 C[i][k] != C[p][k] 인 k가 존재한다면 k번열을 칠하고 나서 i번행을 칠해야 한다는 사실이 도출된다. C[i][k] == C[p][k] 인 k가 존재한다면 i번행을 칠하고 나서 k번열을 칠해야 한다는 사실이 도출된다. 이런 'X를 칠하고 나서 Y를 칠해야 한다' 는 사실들을 방향그래프로 모델링할 수 있다. 이렇게 만든 방향그래프에 사이클이 존재한다면 칠하는 순서를 정할 수 없는 것이고 사이클이 없다면 적당히 순서를 정할 수 있게 된다. 전부 칠하는 최소횟수는 (열 개수) + (p번행과는 구성이 다른 행 개수) 가 된다.