1. 깊이 우선 탐색
트리나 그래프를 탐색하는 기법중 하나로 시작 노드로부터 깊이를 우선으로 탐색하는 알고리즘이다.
1.현재 노드를 방문한 것으로 표시한다.
2.방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색한다.
3.더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking) 한다.
4.모든 정점을 방문할 때까지 프로세스를 반복한다.
어떤 노드에 대해서 그 노드의 값을 탐색 한 후에 이 값을 탐색 했다.
라고 마킹을 해두는 것이다.
이런 식으로 하나씩 탐색을 하면서 해당 구역이 매핑이 되었음을 확인하고 다음 구간을 확인한다.
이때 확인한 구간 밑에 노드들이 또 있다면 그 노드들을 전부 다 탐색할 때까지 다른 방향의 노드로 가지 않는다.
=> 왼쪽을 먼저 탐색을 한다고 했을 때, 왼쪽의 끝까지 전부다 탐색을 하고나서 오른쪽을 탐색한다.
2. 백트래킹
재귀적으로 문제를 해결하는데 현재 재귀를 통해서 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고 해당 상태가 위배된다면 해당 상태를 제외하고 다음 단계로 넘어간다. => 모든 경우의 수 탐색
이런식으로 조건에 맞지 않는다면 예전으로 돌아가는데...
나는 이것이 처음에는 이해가 되질 않았는데, 결국은 마트료시카와 비슷한 것이다.
첫번쨰로
이런 식으로 dfs를 선언하고 안에서 재귀 호출 함수를 돌게되면
첫번쨰로 선언한 dfs(재귀 호출한 dfs) 가 들어가 있게되는 것이다.
그렇기에 재귀 호출한 dfs가 끝나기 전까지는 다음 문장이 실행이 되지 않게 된다.
이걸 왜 몰랐을까...
ㅇㅇ