Computer Science/Algorithms
2023. 1. 12.
[알고리즘] 백트래킹 (BackTracking)
백트래킹이란? 재귀적으로 문제를 풀어나가는 알고리즘 특정 조건에 위배되면 가지치기를 함 ( 특정 노드를 제외하는 것 ) DFS를 사용하는 알고리즘 중에 백트래킹이 있다. ( DFS는 최적의 경로를 반환한다.) 백트래킹과 DFS의 차이점 DFS는 가능한 모든 경로를 탐색하므로, 가지치기를 하지 않는다. 백트래킹은 현재의 경로가 불필요하다면 다시 되돌아간다. DFS에서 조건문과 재귀를 통해 코드를 구현하면 백트래킹을 구현할 수 있다. 백트래킹의 구현, 예제 결론적으로 백트래킹은 DFS를 수행하고, 유망한 노드인지를 판단한 뒤 하위 노드로 이동하는 형식이다. 백트래킹을 이용한 문제 백준 - N과 M (1) https://walk-cat-dev.tistory.com/57