DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프나 트리 탐색에서 사용하는 대표적인 탐색 알고리즘이다. 두 알고리즘 모두 특정 노드를 방문하고, 그 노드와 연결된 다른 노드들을 탐색하는 방식으로 동작한다. DFS는 깊이를 우선으로 탐색하고, BFS는 너비를 우선으로 탐색한다.
1. DFS (Depth-First Search, 깊이 우선 탐색)
DFS는 탐색할 때 가능한 한 깊게 들어가는 방식으로 탐색한다. 즉, 한 경로를 따라 끝까지 가고, 더 이상 갈 곳이 없으면 다시 돌아와 다른 경로를 탐색한다. 이 방식은 재귀나 스택을 사용해 구현할 수 있다.
DFS 예시: 그래프 탐색
function dfs(graph, start, visited = new Set()) {
// 현재 노드 방문 처리
visited.add(start);
console.log(start);
// 현재 노드와 연결된 노드들을 재귀적으로 방문
for (let neighbor of graph[start]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
// 그래프 표현 (인접 리스트)
const graph = {
1: [2, 3],
2: [4],
3: [5],
4: [],
5: []
}
dfs(graph, 1); // 출력: 1 2 4 3 5
DFS의 시간 복잡도
- 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
- 그래프의 모든 노드를 방문하고 모든 간선을 처리해야 하기 때문에, 위와 같은 복잡도를 가진다.
2. BFS (Breadth-First Search, 너비 우선 탐색)
BFS는 탐색할 때 가까운 노드부터 차례대로 방문한다. 즉, 특정 노드에서 연결된 모든 노드를 먼저 탐색한 후, 그 다음 깊이의 노드들을 탐색한다. 이 방식은 큐(Queue) 자료 구조를 사용해 구현한다.
BFS 예시: 최단 경로 탐색
function bfs(graph, start) {
const queue = [start]; // 탐색할 노드를 저장할 큐
const visited = new Set(); // 방문한 노드를 저장할 집합
visited.add(start);
while (queue.length > 0) {
const node = queue.shift(); // 탐색할 노드를 큐에서 꺼냄
console.log(node);
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
// 그래프 표현 (인접 리스트)
const graph = {
1: [2, 3],
2: [4],
3: [5],
4: [],
5: []
};
bfs(graph, 1); // 출력: 1 2 3 4 5
BFS의 시간 복잡도
- 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
- 모든 노드와 모든 간선을 한 번씩 방문하기 때문에 DFS와 마찬가지로 같은 복잡도를 가진다.
DFS와 BFS의 차이
- 탐색 방식: DFS는 깊이 우선으로 탐색하며, BFS는 너비 우선으로 탐색한다.
- 구현 방식: DFS는 재귀나 스택을 사용하고, BFS는 큐를 사용해 구현한다.
- 사용 사례:
- DFS는 경로 탐색(예: 미로 찾기)나 백트래킹이 필요한 문제에 적합하다.
- BFS는 그래프에서 최단 경로를 찾는 문제에 적합하다.
예시 문제
1. 미로 찾기
문제: N x M 크기의 미로가 주어질 때, 출발점에서 도착점까지 최단 경로를 찾으세요. 벽은 통과할 수 없으며, 상하좌우로만 이동할 수 있습니다.
// BFS
function shortestPath(maze, start, end) {
const directions = [[0, 1], [1, 0], [0, -1], [1, 0]];
const queue = [[start, 0]]; // [현재위치, 이동거리]
const visited = new Set();
visited.add(start.toString());
while (queue.length > 0) {
const [[x, y], distance] = queue.shift();
if (x === end[0] && y === end[1]) return distance;
for (let [dx, dy] of directions) {
const newX = x + dx;
const newY = y + dy;
if (newX >= 0 && newY >= 0 &&
newX < maze.length && newY < maze[0].length &&
maze[newX][newY] === 0 && !visited.has([newX, newY].toString())
) {
visited.add([newX, newY].toString());
queue.push([[newX, newY], distance + 1]);
}
}
}
return -1; // 도착할 수 없는 경우
}
const maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
];
console.log(shortestPath(maze, [0, 0], [4, 4])); // 출력: 8 (최단 경로 거리)
2. 섬 개수 세기
문제: 2차원 배열에서 육지를 1, 바다를 0으로 나타내는 섬의 지도에서, 섬(연결된 1의 집합)의 개수를 구하세요.
// DFS
function numIslands(grid) {
let count = 0;
function dfs(grid, x, y) {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === '0') {
return;
}
grid[x][y] = '0'; // 방문한 곳은 0 처리
dfs(grid, x + 1, y);
dfs(grid, x - 1, y);
dfs(grid, x, y + 1);
dfs(grid, x, y - 1);
}
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
const grid = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
];
console.log(numIslands(grid)); // 출력: 3 (3개의 섬)
반응형
'알고리즘 & 자료구조' 카테고리의 다른 글
| [알고리즘] 그리디 알고리즘 (Greedy Algorithm) (0) | 2020.09.05 |
|---|---|
| [알고리즘] 동적 계획법 - Dynamic Programming (0) | 2020.08.23 |
| [알고리즘] 이분 탐색 - Binary Search (0) | 2020.08.18 |
| [알고리즘] 삽입정렬 (0) | 2020.08.17 |
| [알고리즘] 재귀호출 (0) | 2020.08.17 |