처음에 어떻게 접근해야할지 몰라서 해설을 찾아봤습니다. 해설대로 구현해보려 하는데 제가 잘못한 부분이 있는 것 같습니다. 채점을 해보니 틀렸습니다가 나오네요. 생각해봤지만 어느부분이 틀렸는지 잘 모르겠어서 질문남깁니다.

제가 구현하고자 했던 방식은 아래와 같습니다.

먼저, 동적계획법을 푸는 재귀함수를 만들고자 했습니다. 

int dfs(int idx, int current, int previous) 

로 설계했고 3차원 DP를 푸는 함수입니다. 

// 1번째 열 ~ idx번째 열까지의 매트릭스에 대해 모든 얼룩을 제거하기 위해 필요한 청소도구의 최소 갯수를 반환한다.
// current : 현재 열의 청소상태(단, 얼룩의 상태를 보기 위해선 map 배열을 참조해야함).
// previous : 이전 열(idx-1)의 청소상태(단, 얼룩의 상태를 보기 위해선 map 배열을 참조해야함).

dfs 함수 내에서 idx번째 열을 처리할 때 3 by 3 청소도구를 두게 되는데 이 때 뒤쪽 열(idx+1, idx+2)에는 영향을 끼치지 않고 현재 열(idx) 포함 오직 이전 열(idx-1, idx-2)에만 영향을 끼칠 수 있다고 생각했습니다.

그래서 아래 그림과 같이 idx 열에 대해 작업 중 일땐 오직 빨간색, 파란색과 같은 형태로만 얼룩들을 지울 수 있다고 생각했습니다.

재귀 함수내에서 다음 함수를 호출할 때는 dfs(idx-1, , ) 형태로 이루어지게 되고 그러면 idx 열에는 얼룩이 없음이 보장되어야 한다고 생각했습니다. 그래서 이를 확인하는 작업이 dfs() 함수 내에서 isPossible()을 호출함으로써 검사하게 됩니다.

bool isPossible(int idx, int current, int covered) 함수 내에서는 idx열에 얼룩이 있는지 없는지 검사합니다. current는 빨간색이나 파란색 청소도구를 두기 전 상태이고 covered는 빨간색 또는 파란색과 같은 청소도구로 현재 열을 어떻게 채울지 나타내는 변수입니다.

isPossible 함수가 true를 반환할 때만 dfs 함수는 idx-1에 대해 호출하도록 구현했습니다.

제가 해설의 어느 부분을 잘못이해하고 잘못 코딩한 것인지 한번 봐주시면 감사하겠습니다.

-------------------------------------------------------------------------------------------------------------------------

아래 그림은 제가 input을 어떻게 처리했는지 나타내는 그림입니다. 2차원 배열이 아닌 int 형의 1차원 배열을 선언했습니다. 1차원 배열 각각의 정수에서 특정 번째 비트가 2차원 배열에서의 행 역할을 하도록 했습니다. 그리고 얼룩은 비트 0으로 표현했습니다.

0번째 열에 색을 채워 넣은 이유는 중요하지 않다는 의미를 나타내기 위해서입니다. 어짜피 1열 ~ Col열까지만 고려하기 때문에 0번째 열은 중요한 정보가 아니라고 생각했습니다.

아래는 저의 코드 입니다. 긴글 읽어주셔서 감사합니다.