dfs vs 백트래킹
- dfs는 그래프를 탐색하는 방법론이고, 한 방향으로 나아가며 탐색하는 방법으로, 막다른길 도착하면(더이상 진행 못하면,) 방문하지 않은 노드로 돌아와서 , 새로운 방향으로 설정해서 깊이있게 탐색함.
그런데 이것이 후퇴를 한다는 개념은 아니고, 방문체크 해제하지 않음.
- 백트래킹은
그래프 탐색이 아닌상태공간트리 로서 , 모든 경우의 수를 찾는 알고리즘으로,
dfs와 동일하게 깊이있게 진행중에 조건이 맞지 않다면, 하위 노드 확인하지 않고, 바로 후퇴작업을 하고, 방향을 재설정해서 탐색함.
후퇴할때 방문체크를 해제해서 , 새로운 경우의 수 찾을 때 다시 활용함.
문제 분석
- 주어진 항공권을 모두 사용해야 한다. 는 조건이 핵심이다.
-
dfs를 진행했는데, 복귀를 하지 않으므로, 앞선 인덱스로 진행했는데, 연결되지 않아서, 타겟으로 돌아와서 진행하는 것은 연결된 것이 아니다.
-
모두 하나로 a -> b 순으로 연결된것을 보여줘야 한다.
=> 즉 dfs가 아니라, 백트래킹을 진행해야 함.
목적
- dfs는 경로 상관 없이 진행함.
- 백트래킹은 모든 경로를 확인함.
시간복잡도
- 1) dfs는 모든 정점과 간선을 이용해 탐색하므로 V + E
- 2) 백트래킹은 해당 타겟값을 선택하냐? 선택하지 않냐? 이므로 2의 n승이다.
또는 순열과 같은 상황도 발생하므로 n! 이다.
하지만 여기서 가지치기를 하므로, 더 절약될 것으로 생각합니다.
예를 들면 1,2,3,4,5 중에서 3개를뽑아 순열로 표현하라는 식.
상태 공간트리
실제 풀이 : 입출력을 너무 믿지 말자.
-
솔직히 문제에서 주어진 입출력 예제만 보면, dfs로 풀면되지 않을까? 생각함.
-
1) dfs 코드 어찌 저찌 해서 작성함.
-> 틀렸다.
-
2) 심지어 종착지만 있는것도 반례 처리했는데..
만약 내가 dfs를 한다고 하자.
1번 : 문제에 주어진 정보대로.
-
ICN->ATL->ICN 복귀를 하고 있다.
dfs 코드대로 생각해보면, 다시 복귀를 해서 탐색진행을 하고 있는데, 이거는 복귀냐? 아니면 갈곳 없어서, 다시 돌아와서 진행하는거냐? 생각할 수 있다. -
그런데 다른 방법을 또 제시하고 있다.
즉, 방문체크를 해제하고 모든 경우의 수를 확인하고 있으니 백트래킹으로 가야한다.
2번 : 정렬을 먼저 할까? 생각함.
- 문제에서 정렬대로 나오라고 해서 정렬한 상태에서 시작할까??
문제의 제한사항을 보면, 주어진 항공권을 모두 사용해야 한다.인데
-> 그렇다면, 논리적으로 생각해보면,
굳이 정렬한 대로만 했는데, 오히려 이때는 모든항공권을 사용하지 못할수도 있지 않을까??? 라는 생각을 함.
백트래킹을 묻는 문제다.
-
입출력 예제 1,2번만 보고 dfs를 선택했는데 틀림.
-
0) 입출력만 가지고 판단하지 말자.
-> 맹신하지 말자... -
1) 이러한 경우가 있다.
-> 일반적인 dfs로는 풀수 없다.
후퇴를 해야하므로, 백트래킹으로 가야한다.
-
2) 문제의 조건 중에 "티켓을 다 써야한다고" 했다.
-> 그런데 1번의 그래프처럼 순환트리구조로 되어 있을 수 있음을 생각해야 한다.
-
입출력 1번 단일방향으로 되어 있따.
-
3) 2번 예제를 그려보면, 일반적인 dfs로는 불가하고 백트래킹해야 한다는 생각을 해야 함.
-> icn에서 atl갔다가 다시 icn와서 sfo로 가는 경로는 진행, 후퇴,진행하는 순이므로, 백트래킹을 먼저 떠올려야 한다.
dfs vs 백트래킹
- 제미나이
결론
: 복귀를 가지고 있으면 dfs를 생각하지 말고, 백트래킹 생각하자.
여행경로
- 주의할 점
: 예외처리 .
-> 오로지 종착점만 있는 경우도 있다. 이를 예외처리해야 함.
