[일반] 너비우선탐색으로는 완전 탐색 불가?

[익명(59.14)]

깊이로는 백트래킹 써가지고 완탐 하잖아.

너비는 안되나

[익명(182.227)]

깊이 우선 너비 우선 이게 유일한 차이점임

[익명(59.14)]

글쿠낭

[익명(110.76)]

완전탐색을 못하면 탐색이라고 못하지

[익명(59.14)]

된다는 거임?

[익명(110.76)]

ㅇㅇ

[dddd(61.74)]

모든 정점 탐색되냐고?

[익명(59.14)]

ㅇㅇ

[dddd(61.74)]

너비우선탐색이 가중치없는 그래프일 때 최단경로 찾게 해주잖음. 거리가 1에 있는 정점부터 방문한다는 얘기고 가장 긴 거리까지 탐색하면 모든 정점 방문하는거잖음. 이러면 모든 정점 탐색한거 아닌가

[dddd(61.74)]

*연결그래프일때

[익명(118.235)]

왜 안된다 생각하는지가 궁금한데 방문순서 차이만 있는거야

[익명(59.14)]

보통 완탐 문제에서 queue를 본적이 없어서

[익명(110.76)]

dfs가 bfs보다 구현이 쉬워. 최단거리가 중요하면 bfs로 탐색하지

[익명(121.153)]

dfs, bfs 메모리 차이도 심함 n개 정점 이진트리라 치면 dfs 공간복잡도 log n 인데 bfs는 n 이잖아