백준 12869 뮤탈리스크 풀이 (파이썬) dfs는 안되고 bfs는 되는 dp문제

코드만 궁금한 분은 깃허브 링크 눌러주세요..!

 

일단 나는 이 문제를 처음에 dfs로 풀었었다. 근데 아무리 해도 안돼서;(특히 25%에서 계속 안됨) 이유를 생각해봤다. 문제에서 경우의수가 너무 많은 만큼 dp로 3차원 리스트를 만들어서 이미 확인한 경우는 확인 안 하는 식으로 해서 문제를 풀어야 한다. 근데 이 때 이미 확인 안하는 것은, 이전에 확인한게 최선이라는 확답이 있는 경우에만 가능하다. 그런데 dfs로 문제를 풀면 그때까지의 계산 횟수가 얼마이든간에 우선적으로 많은 부분을 방문하게 되고, 이후에 계산 횟수가 더 적게 같은 상태에 도달할 수 있더라도 그 부분을 방문하지 않아버림으로 인해 오류가 나게 된다. 

 

dfs라도 방문/비방문 리스트가 아니라 어떤 값의 쌍까지 오는데에 걸린 계산횟수를 저장해두고 그것보다 작으면 다시 계산하는 식으로 하면 문제가 제대로 풀릴 것 같다.

 

아무튼 25%부분에서 오류가 나는 사람이 있다면 위에 내가 얘기한 문제이므로 그 부분을 해결하면 아마 풀 수 있을거라고 생각한다. 나도 혼자 풀지는 못했고 다른 풀이를 조금 참고했는데, 특히 길이가 2 혹은 1인경우 0을 더해서 길이가 3인 리스트로 만드는 부분이 인상적이였다. 길이가 다른 경우에 어떻게 해야하나 고민을 많이 했는데 이렇게 하면 경우를 따로 나누지 않아도 된다. 그리고 음수값이 나오는 경우 이를 0으로 바꿔주는 부분도 좋았다. 요새 코딩테스트 문제를 전보다 좀 덜 풀었더니 감이 떨어진건가 싶기도 하고. 역시 공부는 꾸준히 해야하나보다,,