evilsith   8달 전

dfs로 시간초과나서 bfs로 풀긴 풀었습니다.
근데 이 문제에서 dfs를 사용하면 안되는 이유가 무엇인지 궁금하네요?
dfs도 시간초과 안나고 통과할꺼같은데..

어떠한 조건이 이문제를 bfs로만 가능하게끔 하는것인지 설명해주시면 감사하겠습니다.

yukariko   8달 전

https://www.acmicpc.net/problem/2178

이 문제가 bfs로 풀리는것과 같지 않을까요?

bfs는 한번 간 정점을 다시 반복하지 않아도 되지만

dfs는 어떤 정점을 거쳐서왔는지에 따라 다를테니까요

그런데 이 문제는 메모이제이션해주면 dfs로도 풀릴거같네요

yukariko   8달 전

풀어보니 메모이제이션 dfs로 풀립니다.

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