글 읽기 - 이문제가 dfs로 안되는이유가 무엇인가요??

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

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

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

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

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

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

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

어떤식으로 해야 메모이제이션으로 풀리나요 ??

호기심이 생겨서 한번 구현해봤는데 메모이제이션 안해도 dfs로 풀리는거 같아요.

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

Baekjoon Online Judge