skins346   3년 전

백트래킹이란 DFS를 말하는건가요?

BFS는 백트래킹이랑고 하지 않는건가요?

simm4256   3년 전

기본적으로 백트래킹은 '가능한 모든 방법을 탐색'한다는 데 그 기본 아이디어가 있습니다.

이 아이디어의 구현은 DFS, BFS 둘 다 가능한 방법입니다.

다만, 백트래킹은 보통 '불가능한 방법'임을 인지한다면 이전 상태로 돌아오는 작업이 필요한데

이는 큐를 사용하는 BFS보다는 스택(혹은 재귀)을 사용하는 DFS가 더 편하기 때문에 일반적으론 DFS를 사용합니다.

skins346   3년 전

되돌아오는 개념은 BFS를 사용할때 불편한게 아니라 불가능 아닌가요? DFS는 깊이 우선탐색이니 가능하지만

simm4256   3년 전

큐에 노드를 집어넣을 때 이전 노드에 대한 정보를 집어넣으면 됩니다. 실제로 최대유량 알고리즘 중 애드몬드 카프 알고리즘이 이 방법을 사용합니다.

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