코딩테스트/알고리즘
Backtracking
모든 경우의 수를 전부 고려하는 알고리즘이며, 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘 한정 조건 백트래킹은 모든 경우의 수에서 한정 조건에 유망한 promissing 경우를 탐색하는 것이기 때문에 완전탐색기법인 BFS 나 DFS 모두 구현이 가능하다. 하지만 백트래킹의 특성에서 한정 조건에 부합하지 않다면 이전 수행으로 돌아와야하기 때문에 BFS보다 DFS가 구현에 편하다. 백트래킹을 구현할 때 가장 중요한 것은 한정 조건이다. 한정 조건을 걸어 완전 탐색에서 유망하지 않은 시도를 걸러내는 것이 백트래킹의 본질이다. n, m = map(int, inpu..
