dhedaa   7년 전

bfs는 너비우선탐색 dfs는 깊이우선탐색 이렇겐 배웠고....

두 알고리즘의 특징, 성질에 대해서는 기본적으로 이해했는데....

문제를 풀때, 그 문제가 이 두 알고리즘중 어떤걸로 풀어야 적당하게 푸는지 헷갈릴때가 많습니다.

아직 내공이 많이 없어서 그런가봐요...

그래서 요즘엔 재귀를 썼을때 메모리를 많이 쓰지 않을것같은 문제는 dfs를 쓰고, 

큐를 써야할꺼같은 문제는 bfs를 쓰는 방식으로 문제를 풀고있는데요.

다른분들은 문제를 보고 아 이건 dfs로 풀면 되겠다 bfs로 풀면 되겠다라고 어떻게 판단하시는지 궁금합니당.

jason9319   6년 전

DFS로 전처리를 해줘야 하는 경우나 DFS를 이용하는 알고리즘이 아닌 단순히 그래프에서 모든 정점을 탐색하는 용도라면 DFS,BFS 중 편하신걸 사용하셔도 어지간한 문제들은 AC받으실 수 있을거에요. 

단 가중치 없는 그래프의 최단 경로문제는 BFS로만 접근하셔야됩니다.

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