hong4243   2년 전

BFS와 DFS와 DP를 어떤 상황에서 적용하는게 맞는지 궁금합니다.


EX)

DFS  ->그래프 알고리즘(함수)

BFS ->그래프 알고리즘(정점)


->최단거리 알고리즘 (모든 가중치가 1인 경우)

1. 최소 비용을 찾는 문제 2. 문제의 상태를 정의 (= 정점) 3. 움직일때 가중치가 무조건 1로 4. 문제의 제한 -> 정점 개수의 제한이 적어야 한다. (= 시간복잡도를 알아야 한다)  사용조건) ---->최소비용,상태가 정점이고, 가중치가 1이 나온다.

5. 두가지 (몇번을 방문 했는지, ~을 방문했는지 확인할 2개의 배열이 필요하다) 6. 중복된 행동을 하면 안된다.


DP (점화식)

이런식으로요. 고수님들 부탁드립니다!

chogahui05   2년 전

문제 상황에 따라서 달라서 어떻게 답해야 할 지 잘 모르겠습니다.


bfs + dp라던지 dfs + dp 이런 식의 문제도 있고요.

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