백트래킹1 백트래킹 Javascript DFS 문제 풀이를 보다 보면 dfs로 탐색을 하다가 탐색이 끝나면 방문 했던 노드나, 값을 취소하는 코드가 있는데 예를 들어 아래 코드의 경우 울타리를 세울수 있는 경우 울타리를 세우고 dfs 탐색을 한 다음 끝나면 울타리를 제거하고 for 문을 계속 돌아준다. 나는 지금까지 책 풀이를 볼 때 이런 경우 백트래킹이라고 딱히 명시를 안해줘서 이런 경우는 그냥 이렇게 풀어야 되는구나로 알고 있었는데 이런 풀이가 백 트래킹이란 것을 오늘 알았다. 백트래킹이란? 해결책을 구하기 위해, 후보군을 구하다가, 해당 후보군이 문제의 조건을 만족하지 않으면, 다시 이전의 상태로 돌아가 다른 후보군을 찾는 기법이다. map에서 빈 곳일때(0) 울타리를 세우는(1) 과정이다. dfs 탐색을 하여 해당 함수가 끝나면 울타리.. 2023. 4. 3. 이전 1 다음
