sgc109   1년 전

dfs로 미로를 탐색하는 코드를 짜봤는데


M,N 이 각각 100일때 너무 많은 경우의수가 생겨버려서(물론 이 보다 작은 값에서도 너무 많겠지만..)


런타임 에러가 뜹니다.. 쓸데없이 더 긴 경로를 계속 계산을 한다는 문제점이 있는 것같아서


dp 를 사용해서 지금까지 걸린 거리를 기록해서 또 다음번에 그 칸에 왔을때 거리가 더 길다면 그만 탐색하도록 작성하려고했으나


대부분의 경우 더 긴 경로를 먼저 계산해서인지 그다지 효율을 증가시켜주진못했습니다..


여기서 어떻게 하면좋을지 모르겠습니다. 조언 부탁드립니다.


@hongjun7

휴리스틱을 섞은 DFS보다 BFS가 이런 문제에서는 훨씬 빠른 솔루션이 됩니다.

BFS를 이용해 작성해보시면 금방 정답 뜨실거예요

sgc109   1년 전

portableangel 아 그렇군요! 최근에 그래프 이론 공부하면서 DFS 를 익혀서 관련문제 찾아서 풀고있었는데 DFS 가아닌 BFS 문제였을줄은..

감사합니다!

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