핵심

• 일직선으로 그리기 => 한붓그리기
  => 백트래킹.

dfs vs 백트래킹

• dfs는 그래프를 탐색하는 방법론이고, 한 방향으로 나아가며 탐색하는 방법으로, 막다른길 도착하면(더이상 진행 못하면,)
• 진행한 노드로 다시 돌아와서 방문하지 않은 노드를 향해 새로운 방향으로 설정해서 깊이있게 탐색함.

그런데 이것이 후퇴를 한다는 개념은 아니고, 방문체크 해제하지 않음.

• 백트래킹은 그래프 탐색이 아닌 상태공간트리 로서 , 모든 경우의 수를 찾는 알고리즘으로,
  dfs와 동일하게 깊이있게 진행중에 조건이 맞지 않다면, 하위 노드 확인하지 않고, 바로 후퇴작업을 하고, 방향을 재설정해서 탐색함.

후퇴할때 방문체크를 해제해서 , 새로운 경우의 수 찾을 때 다시 활용함.

=> 아래에 dfs그림과 백트래킹 진행 그림이 있다.

이 문제의 핵심은 이부분.

• dfs의 경우, 일직선으로 진행하지 않는 그래프다.
  

• dfs를 하게 되면, 1->2->3->4 가 출력된다. (1로 다시 복귀해서)
  -> 일직선이 아니다!!
  

• 그런데 문제의 요구하는 바는 그래프가 이렇게 되어있어야 함.
  

• -> 즉 이 문제는 방향성을 가지고 각 정점들이 서로 일직선으로 연결되어 있는 경로를 만드는 것이다.

• 그에 반해서 dfs는 일직선이 아니다.

• 일직선으로 되어 있는 경로를 찾은 작업인 백트래킹을 해야 한다!

차이를 분명하게 하자.

• [a,b] 는 a에서 b로 가는 항공권이고, 이것을 모두 사용해야 하고, 방문하 수 없는 경우가 없으므로,
  => 일직선 형태인 한붓 그리기로 접근해야 함.
  

한붓 그리기