깊이우선탐색

[알고리즘] DFS (깊이우선탐색)

1. DFS(깊이 우선 탐색)? DFS(Depth-First-Search)는 깊이 우선 탐색으로 스택 또는 재귀를 통해서 주로 구현이 됩니다. 하나의 인접노드에 대해 모든 인접노드를 다 탐색한 뒤 다음 인접노드로 넘어가는 방식으로, 해당 노드에 대해 방문여부를 체크하는 것이 핵심입니다. 방문여부를 체크하지 않으면 무한루프에 빠질 위험이 있습니다. 2. 기본적인 원리 기본적인 동작 원리는 다음과 같습니다. 현재 노드와 연결된 노드 중 하나의 노드 방문 여부 체크 만약 이미 방문된 노드라면, 패스 / 만약 아직 방문되지 않은 노드라면, 방문 현재 노드를 새로 방문한 노드로 변경 인접노드가 없을 때까지 1~3번 반복 더 이상 갈 수 있는 인접 노드가 없을 경우, 가장 최근의 분기점으로 되돌아가 다른 노드 방문..