DFS

DFS(깊이 우선 탐색)의 개념 정리

DFS(Depth-First Search)는 그래프나 트리 탐색에서 사용되는 알고리즘 중 하나로, 한 경로로 가능한 깊이까지 내려간 후에 다시 되돌아와서 다른 경로를 탐색하는 방식입니다. DFS는 재귀나 스택을 사용해 구현되며, 주로 트리 또는 그래프에서 특정 경로나 요소를 찾거나, 연결된 노드들을 탐색하는 데 자주 사용됩니다.

DFS의 동작 과정:

1. 시작 노드에서 탐색을 시작하고, 해당 노드를 방문 처리합니다.
2. 인접한 노드들 중 방문하지 않은 노드를 재귀적으로 탐색합니다.
3. 더 이상 탐색할 노드가 없으면, 이전 노드로 돌아와서 다른 인접 노드를 탐색합니다.
4. 모든 경로가 탐색될 때까지 이 과정을 반복합니다.

DFS의 구현 방식:

• 재귀 방식: 함수 호출 스택을 이용하여 재귀적으로 구현.
• 스택 방식: 명시적으로 스택을 사용하여 반복적으로 구현.

DFS를 이용해서 풀 수 있는 문제

• DFS는 연결된 요소들을 탐색하고 그룹화하거나, 경로를 찾는 문제에 자주 사용됩니다.
• DFS를 사용하면 전체 탐색을 효율적으로 수행할 수 있으며, 특정 경로나 패턴을 찾는 데 유리합니다.

 

DFS 문제를 풀 때 알아야 할 핵심 풀이 방법

1. 방문 여부를 추적하는 방식

• DFS 문제에서는 노드를 중복 방문하지 않도록 방문 여부를 기록하는 것이 중요합니다.
• 배열이나 Set 자료 구조를 사용하여 방문 여부를 기록하는 것이 일반적입니다.
• 2차원 배열 문제에서는 보통 visited[x][y]와 같은 형태로 방문 여부를 관리합니다.

const visited = Array.from({ length: N }, () => Array(N).fill(false));

 

2. 재귀 호출 또는 스택 사용

• DFS는 재귀를 이용해 간단하게 구현할 수 있으며, 반복적으로 깊이 탐색을 진행할 수 있습니다.
• 문제에 따라 스택을 명시적으로 사용하는 방식도 가능합니다.

3. 어떤 걸 탐색할 것인가? ⇒ 각 노드와 인접한 노드를 탐색!

1. 인접 리스트 객체에 각 노드에 인접해있는 노드를 정리예시 : 교재의 몸풀기 문제

방향이 있는 그래프 (Directed Graph)

• 방향이 있는 그래프에서는 간선이 특정 방향으로만 연결됩니다. 즉, (u, v)라는 간선이 있으면 u → v로만 이동할 수 있고, 반대 방향(즉, v → u)으로는 이동할 수 없습니다.
• 이때, 인접 리스트를 만들 때 한쪽 방향만 추가해야 합니다.

graph.forEach(([u, v]) => {
  if (!adjList[u]) adjList[u] = [];
  adjList[u].push(v);
});


// 결과
{
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
}

 

예시 : “바이러스” 문제에 적용한 DFS

https://www.acmicpc.net/problem/2606

방향이 없는 그래프 (Undirected Graph)

• 방향이 없는 그래프에서는 간선이 양방향으로 연결됩니다. 즉, (u, v)라는 간선이 있으면 u ↔ v로 양방향 이동이 가능합니다.
• 따라서, 양쪽 모두 인접 리스트에 추가해야 합니다.

graph.forEach(([u, v]) => {
  if (!adjList[u]) adjList[u] = [];
  adjList[u].push(v);

  if (!adjList[v]) adjList[v] = [];
  adjList[v].push(u);
});

• 이 경우 u → v뿐만 아니라 v → u도 추가되므로, 양방향 이동이 가능합니다.

2. 탐색 방향 지정

예시: "단지번호붙이기" 문제에 적용한 DFS

https://www.acmicpc.net/problem/2667

• 상하좌우 또는 8방향 등으로 이동할 수 있는 경우, 방향 벡터를 사용하는 것이 유용합니다.
• 예를 들어, 상하좌우로 이동하는 경우 [dx, dy]와 같은 방향 벡터를 설정하여 좌표 이동을 처리합니다.예시: "단지번호붙이기" 문제에 적용한 DFS
  1. 방문 여부를 체크: visited 배열로 방문 여부를 관리.
  2. DFS 탐색: 연결된 집들을 상하좌우로 탐색하면서 단지 크기를 계산.
  3. 탐색 경로 설정: 상하좌우로 이동하기 위한 방향 벡터를 설정하여 모든 경로 탐색.
  4. 결과값 저장: 각 단지의 크기를 계산하고 이를 정렬하여 출력.

const directions = [
  [-1, 0], // 상
  [1, 0],  // 하
  [0, -1], // 좌
  [0, 1]   // 우
];

4. 연결된 모든 노드 탐색

• 연결된 모든 노드(또는 좌표)를 탐색하는 문제가 많습니다. 한 번 방문한 곳은 다시 방문하지 않게 해야 하며, 하나의 연결된 그룹(예: 단지, 섬 등)이 얼마나 큰지 측정하는 것이 핵심입니다.
• DFS를 통해 해당 그룹의 크기나 성질을 계산하고, 결과값을 저장합니다.

5. 경계 조건 처리

• DFS 문제를 풀 때는 좌표나 노드의 경계를 벗어나지 않도록 범위 검사를 철저히 해야 합니다.
• 배열을 다루는 경우, 배열의 크기를 초과하거나 음수 좌표로 이동하지 않도록 조건을 설정해야 합니다.

  // 상하좌우로 이동
  for (const [dx, dy] of directions) {
    const nx = x + dx;
    const ny = y + dy;

    // 배열 범위 안에 있고, 방문하지 않았으며, 집이 있는 경우만 이동
    if (nx >= 0 && nx < arr.length && ny >= 0 && ny < arr.length) {
      if (!visited[nx][ny] && arr[nx][ny] === "1") {
        count += dfs(nx, ny); // 연결된 집 개수를 누적
      }
    }
  }

6. DFS의 시간 복잡도

• DFS의 시간 복잡도는 보통 O(V + E)로, V는 노드의 수, E는 간선의 수입니다. 이는 노드와 간선을 한 번씩 방문하기 때문입니다.
• 2차원 배열에서는 보통 O(N^2)의 시간 복잡도가 발생합니다.