[JS] 코딩테스트 대비 DFS(깊이 우선 탐색) & BFS(너비 우선 탐색)

🚀 DFS(깊이 우선 탐색) & BFS(너비 우선 탐색) 개념 정리

DFS와 BFS는 그래프 탐색 알고리즘으로, 그래프나 트리 구조에서 원하는 데이터를 찾거나 전체 노드를 방문할 때 사용.

🔹 1. DFS(Depth-First Search, 깊이 우선 탐색)

DFS는 최대한 깊이 내려가면서 탐색하는 방식.

 

📌 특징:

• 한 방향으로 계속 탐색하다가 더 이상 갈 곳이 없으면 되돌아와서 다른 경로 탐색
• 스택(Stack) 또는 재귀(Recursion)를 사용
• 그래프의 모든 노드를 방문할 때 유용
• 백트래킹(Backtracking) 문제에서 많이 활용

📌 DFS 동작 방식:

1. 현재 노드를 방문하고 방문 표시
2. 방문한 노드의 자식 노드(연결된 노드) 중 방문하지 않은 노드로 이동
3. 더 이상 갈 곳이 없으면 뒤로 돌아감(백트래킹)
4. 모든 노드를 방문할 때까지 반복

🎯 DFS 예제 (재귀 방식)

const graph = {
  1: [2, 3, 4],
  2: [5, 6],
  3: [],
  4: [7],
  5: [],
  6: [],
  7: []
};

const visited = new Set();

function dfs(node) {
  if (visited.has(node)) return;  // 이미 방문한 노드면 리턴
  console.log(node);  // 현재 노드 출력
  visited.add(node);  // 방문 표시

  for (const neighbor of graph[node]) {  // 연결된 노드 탐색
    dfs(neighbor);
  }
}

dfs(1);

 

🔹 실행 결과:

1  
2  
5  
6  
3  
4  
7

👉 1 → 2 → 5 → 6 → 3 → 4 → 7 순서로 탐색됨.

 

 

자세한 코드풀이

1️⃣ 그래프 정의

const graph = {
  1: [2, 3, 4],  // 1번 노드는 2, 3, 4번 노드와 연결됨
  2: [5, 6],     // 2번 노드는 5, 6번 노드와 연결됨
  3: [],         // 3번 노드는 연결된 노드가 없음
  4: [7],        // 4번 노드는 7번 노드와 연결됨
  5: [],         // 5, 6, 7번 노드는 더 이상 연결된 노드가 없음
  6: [],
  7: []
};

 

• 그래프는 객체로 표현했고, 각 키(노드 번호)에 연결된 노드들의 배열을 저장했어.
• 예를 들어, 1: [2, 3, 4]는 노드 1이 2, 3, 4와 연결되어 있다는 뜻이야.

2️⃣ 방문한 노드를 저장하는 Set (중복 방지)

const visited = new Set();

 

 

• Set은 중복을 허용하지 않기 때문에, 방문한 노드를 저장해서 중복 탐색을 방지할 수 있어.
• 방문한 노드를 기억하지 않으면 무한 루프에 빠질 수도 있어!

3️⃣ DFS 함수 구현

const graph = {
  1: [2, 3, 4],
  2: [5, 6],
  3: [],
  4: [7],
  5: [],
  6: [],
  7: []
};

const visited = new Set();

function dfs(node) {
  if (visited.has(node)) return;  // 이미 방문한 노드면 리턴
  console.log(node);  // 현재 노드 출력
  visited.add(node);  // 방문 표시

  graph[node].forEach(neighbor => {
    dfs(neighbor);  // 재귀 호출
  });
}

dfs(1);

function dfs(node) {
  if (visited.has(node)) return;  // 이미 방문한 노드면 리턴
  console.log(node);  // 현재 방문한 노드 출력
  visited.add(node);  // 방문한 노드를 Set에 추가

  for (const neighbor of graph[node]) {  // 현재 노드와 연결된 모든 노드 탐색
    dfs(neighbor);  // 재귀 호출 (DFS 방식으로 탐색)
  }
}

🔍 코드 동작 방식

1. visited.has(node) → 이미 방문한 노드면 리턴
2. 방문한 노드 출력 후 visited에 추가
3. 현재 노드와 연결된 노드를 for 문으로 하나씩 꺼내서 dfs(neighbor) 재귀 호출

4️⃣ DFS 실행

dfs(1);

📌 실행 과정 (스택 구조로 탐색 진행)
1 → 2 → 5 → 6 → (백트래킹) → 3 → (백트래킹) → 4 → 7

💡 실행 결과

1
2
5
6
3
4
7

👉 DFS는 깊이 우선이므로, 한 방향으로 끝까지 탐색 후 백트래킹!

---

🔹 2. BFS(Breadth-First Search, 너비 우선 탐색)

BFS는 가까운 노드부터 탐색하는 방식

📌 특징:

• 모든 인접한 노드를 방문한 후, 다음 깊이의 노드를 탐색
• 큐(Queue)를 사용하여 구현
• 최단 경로 문제에서 많이 사용

📌 BFS 동작 방식:

1. 시작 노드를 큐에 추가하고 방문 표시
2. 큐에서 노드를 꺼내고 해당 노드의 모든 인접 노드를 방문
3. 방문한 노드는 큐에 추가
4. 큐가 빌 때까지 반복

🎯 BFS 예제 (큐 방식)

function bfs(start) {
  const queue = [start];
  const visited = new Set();
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); // 큐에서 노드 꺼내기
    console.log(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

bfs(1);

 

🔹 실행 결과:

1  
2  
3  
4  
5  
6  
7

👉 1 → 2 → 3 → 4 → 5 → 6 → 7 순서로 탐색됨.

---

🔥 DFS vs BFS 차이점 정리

	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 방식	한 경로를 끝까지 탐색 후 백트래킹	현재 노드의 인접 노드부터 탐색
자료구조	스택(Stack) 또는 재귀(Recursion)	큐(Queue)
사용 예시	백트래킹 (미로 탐색, 퍼즐)	최단 경로 문제 (길 찾기)
공간 복잡도	O(V) (재귀 호출로 깊이만큼 메모리 사용)	O(V) (큐에 모든 노드 저장)
시간 복잡도	O(V + E)	O(V + E)

 

📌 정리하자면:

• DFS: 깊이 먼저 탐색 → 백트래킹이 필요할 때 유용
• BFS: 가까운 곳부터 탐색 → 최단 경로 찾기에 적합

---

🎯 DFS & BFS 활용 예제

✅ 1️⃣ 미로에서 최단 거리 찾기 (BFS 활용)

미로에서 최단 거리 찾기는 BFS가 적합해!

function shortestPath(maze, start, end) {
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // 이동 방향 (상, 하, 좌, 우)
  const queue = [[...start, 0]]; // [x, y, 거리]
  const visited = new Set();
  visited.add(start.toString());

  while (queue.length > 0) {
    const [x, y, dist] = queue.shift();
    
    if (x === end[0] && y === end[1]) return dist; // 도착하면 거리 반환

    for (const [dx, dy] of directions) {
      const nx = x + dx, ny = y + dy;
      if (maze[nx]?.[ny] === 0 && !visited.has([nx, ny].toString())) {
        queue.push([nx, ny, dist + 1]);
        visited.add([nx, ny].toString());
      }
    }
  }
  return -1; // 도착 불가능한 경우
}

const maze = [
  [0, 0, 1, 0],
  [1, 0, 1, 0],
  [0, 0, 0, 0],
  [0, 1, 1, 0]
];

console.log(shortestPath(maze, [0, 0], [3, 3])); // 최단 거리 출력

👉 미로에서 BFS를 사용하면 최단 경로를 찾을 수 있어!

 

🏆 정리

1. DFS(깊이 우선 탐색)
   • 한 방향으로 계속 탐색 후 백트래킹
   • 스택 또는 재귀 함수로 구현
   • 백트래킹 문제에서 많이 사용
   • 예: 미로 탐색, 퍼즐 해결
2. BFS(너비 우선 탐색)
   • 가까운 노드부터 탐색
   • 큐(Queue) 를 사용
   • 최단 경로 문제에서 효과적
   • 예: 미로에서 최단 거리 찾기

 

 

 

 

*위 포스팅은 챗GPT 답변을 토대로 작성되었습니다!