히리릿
70
2019-04-30 19:10:12
1
1024

백트래킹과 dfs,bfs의 차이가 뭔가요?


백트래킹이 모든 경우의 수를 탐색한다는 것으로 알고있는데 dfs,bfs는 백트래킹 개념의 방법론이라고 알고 있으면 되나요??

0
  • 답변 1

  • Deer Hunter
    328
    2019-05-01 00:53:52

    Backtracking algorithm은 문제 해결을 위해, 대상을 판단하고 그 결과에 따라 동작하는(거짓일 경우 해당 대상을 제외하고 이전 대상으로 갈 수 있는) 넓은 의미의 문제 해결방법 입니다.

    그리고 DFS, BFS 의 경우는 tree, graph 등에 사용할 수 있는 각각의 구체적이고, 특정한 algorithm 입니다.

    예를 들어 DFS, BFS 에서 node 순회 시 어떤 node를 검사한 결과 요구하는 조건에 맞지 않는 경우, 이전 node를 거쳐 다른 node로 이동할 수 있는데 이것이 backtracking의 예라고 이라고 볼 수 있습니다.

  • 로그인을 하시면 답변 을 등록할 수 있습니다.