m48tank1   8년 전

DFS로 문제를 풀었습니다. 

온라인 채점을 하니 틀렸다고 나오는데, 어디가 잘못되었는지 잘 모르겠습니다.

고수님들 도와주세요

highalps   8년 전

일단, dfs로 그냥 풀어서 제출 하셨으니
아마 시간초과가 났거나 해서 틀렸을거라 추측합니다.

N,M이 100인 경우에는
dfs로 해결하려 할 경우 그 가짓수가 상당해서 제한시간 내에 풀긴 힘듭니다.

따라서 이러한 문제는 bfs로 작성하는 것이 더 빠른 솔루션이 될겁니다. 
priority_queue를 이용해서 해결하면 같은 위치가 두번 들어가는 일이 없어져서 빠르게 풀 수 있습니다.

indioindio   8년 전

DFS로 방문할 때 map[x][y] = '0';를 하고 다시 1로 돌려놓지 않으면 모든 경로를 방문하지 못하게 됩니다.

물론 이렇게 고치면 윗 분 말씀대로 시간초과가 나게 되겠죠.

전부 1인 100 * 100 미로를 상상하시면 왜 시간초과가 나는지 쉽게 알 수 있습니다.

m48tank1   8년 전

코멘트 감사합니다. DFS로는 timeout 이 발생해서 BFS로 해결을 하였습니다. ^^

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