imgosari   7년 전

시간초과가 아니고 틀렸습니다가 계속 나와서 처음 질문을 올리게 되었습니다. (_ _) 코드 한 번 봐주시길 바라요!

제 솔루션은 이렇습니다.
. 으로시작된 부분을 모두 deque에 저장(queue 1번이라고 가정)한 뒤, deque에서 하나씩 빼면서 탐색을 시작합니다.
탐색 방법 : 백트래킹을 이용하여 'O'에 도달할 때 까지 경로를 저장합니다. 그 순간, 초기에 저장한 deque 1번의 요소를 모두 돌면서 'O'에 도달할 때 까지 나아간 경로를 적용하여, 모든 경로에 부합하는지 판단합니다.
예외처리 : 1) 'O'에 도달하였지만, 탐색 횟수가 11이 넘는다면 그 경로는 유망하지 않으므로

                2) 현재의 탐색 횟수가 11이 넘는다면 더 이상 탐색하지 않습니다.

zlzmsrhak   7년 전

반례입니다. 


코드를 보면, 93~99번째 줄에서 구슬은 항상 움직여야 한다는 조건이 있습니다.

저 경우 "답은 있지만, 답대로 움직인 경우 구슬이 어느 위치에 있던 한번이라도 멈추는 경우"는 답이 나오지 않습니다.

imgosari   7년 전

그렇네요.. 제가 dfs 돌리는 과정에서 제자리에 멈추게 되면 그 다음으로 아무데도 못가게 막아놨네요...

유망하지 않다고 판단하는 과정에서 논리상의 오류가 있었던 것 같습니다.


정말 감사합니다. 반례 찾기가 코드 짜는 것 보다 더 힘든데..

많은 도움이 되었습니다.

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