juhyun16   2년 전

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

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

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

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()을 호출함으로써 검사하게 됩니다.

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

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

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

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

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

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

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

koosaga   2년 전

r이 10이 아닌 경우에 처리가 제대로 되는지 확인해 주시고, 또한 Find 함수가 항상 올바른 답을 찾는지 확인해 주세요. 

chogahui05   2년 전

런타임 에러도 납니다. 이 경우는 배열 인덱스를 잘못 참조해서 나타나는 예이겠지요?

문제가 되는 데이터 입니다. 컴파일러는 쓸 수 없어서 ideone에서 확인한 것입니다.

juhyun16   2년 전

두 분의 답변 감사합니다. 곰곰이 생각해보니 아래 그림과 같은 경우가 문제될 수 있겠네요.

idx열 처리할 때 빨간색 청소도구를 두면 idx열에는 얼룩이 존재하지 않게 됩니다. 그래서 isPossible이 true를 반환해줍니다.

prob.JPG

이어서 Find 함수가 다음 상태를 결정짓기 위해 States 배열을 순회할 것입니다. 그런데 idx-1 열의 초록색으로 표시된 얼룩이 빨간색 청소도구로 인해 1로 바뀌게됩니다. 그런데 States 배열에는 연속된 4개 비트가 1인 경우는 존재하지 않으므로 29를 반환하게 됩니다. (0 ~ 28 까지가 유효한 리턴값인데...)

그래서 wrong answer, runtime error 등이 나타나게 되는 것 같습니다.

이 문제를 해결하기 위해 각 열의 상태를 "정확하게" 나타내기 위해 dp 배열을 다음과 같이 선언해야 되나 생각했습니다.

dp[1000+1][(1<<10)][(1<<10)] 

그런데 이렇게 선언해버리면 분명 메모리 초과입니다.

29가지 상태로 나타내야 하는것이 맞는 것 같은데 위의 그림처럼 인접한 네개 비트가 1인 경우에 대해서는 어떻게 처리할 수 있는지 궁금합니다.

koosaga   2년 전

풀이에 대한 이해가 이상하게 된 것 같은데.. 일단 풀이에서 사용된 dp 정의를 그대로 가져 오셨다면 Find 함수를 특별히 만들어 줄 필요가 없습니다. 

juhyun16   2년 전

답변해주셔서 감사합니다~

댓글을 작성하려면 로그인해야 합니다.