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

 

깊이 우선탐색 (Depth-Firtst Search)

 

깊이우선 탐색이란?

루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다.

 

사용하는경우 

모든 노드를 방문 하고자 하는 경우에 이방법을 선택합니다.

 

특징 

1. 자기자신을 호출하는 순환 알고리즘의 형태를 가지고있습니다.

2. 어떤 노드를 방문했었는지 여부를 반드시 검사해야합니다.

 

 

 

DFS의 애니메이션 출처 : 위키피디아

 

 

원리

위의 그림을 보면서 아래 설명을 참고해봅시다.

1. 시작 정점을 1로 설정

2. 1번 탐색 시작 1번과 연결되었고 방문 안한 정점이 어디지? 2번이 있네. 2번으로 가자.

3. 2번과 연결되었고, 방문 안한것? 3번이네. 3번으로 가자.

4. 3번은? 4번이 있네. 4번으로 가자.

5. 4번은? 없는데..?? 그러면 3번으로 다시 올라가자.

6. 3번은? 방문 안한곳이 없네.. 다시 2번... 다시 1번

7. 1번은? 5번이 있네. 5번으로 가자.

-> 이런 식으로 방문 안한 곳이 없을때까지 반복

 

이런식으로 쭉 탐색을 합니다. 한길로 깊이 있게 파고들어가게 되어서 깊이 우선탐색이라고 합니다.

 

 

장단점

• 코드가 직관적이고, 구현하기 쉽습니다.
  -> 사실 일정행동을 계속 반복하는데, 이를 만들어놓고 끝까지 계속 돌려 쓰는 것이기 때문에 비교적 간단하게 코드를 구현할 수 있습니다.
• 특정 조건을 만족하는 한 가지 경로를 찾는 데 적합합니다.

 

단점

• 깊이가 엄청 깊어지면, 메모리 비용을 예측하기 어렵습니다.
  -> 앞서 설명한 것처럼 깊이가 깊어질수록 함수가 하나씩 쌓이는 구조이다. 이 때문에 깊이가 엄청 깊어진다면 스택 메모리가 지나치게 커질 수 있습니다.
• 최적의 조건을 검색하는거보다 무조건 한쪽깊이 서치하기때문에 최단 경로를 알 수 없습니다.

 

 

재귀함수로 구현

// 인접 리스트로 표현된 그래프
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

const visited = new Set<string>();

function dfs(node: string) {
  if (visited.has(node)) return;

  console.log(node); // 방문 처리 (출력)
  visited.add(node);

  for (const neighbor of graph[node]) {
    dfs(neighbor);
  }
}

dfs('A');

 

 

Tip 재귀 함수로 DFS 구현 시 필수 조건

1. 콜 스택 구조

• 재귀 함수는 함수가 호출될 때마다 스택에 쌓입니다.
• 가장 나중에 호출된 함수부터 순차적으로 되돌아갑니다. (LIFO)

2. 종료 조건 필수

• 없으면 무한 재귀 발생합니다. → 스택 오버플로우
• 보통 if (visited.has(node)) return; 같은 식으로 처리합니다.

 

쉽게보면, DFS 호출 흐름 (dfs('A')) 입니다.

 

1. A
   └─ B
       └─ D
           └─ [] → for문 건너뛰고 종료 → D 종료
       └─ E
           └─ F
               └─ [] → 종료 → F 종료
           → E 종료
       → B 종료
   └─ C
       └─ F (이미 visited) → skip
   → C 종료
→ A 종료

 

 

스택 사용 구현

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const DFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...graph[node], ...needVisit];
    }
  }
  return visited;
};

console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]