코딩 테스트 일지 📒
[알고리즘/JAVA] DFS와 BFS
코양이🤍
2024. 11. 13. 01:03
⭐ DFS와 BFS란 무엇인가?
- DFS (Depth-First Search, 깊이 우선 탐색): 그래프나 트리에서 한 경로를 끝까지 탐색하고, 더 이상 탐색할 노드가 없으면 다시 이전 노드로 돌아와 다른 경로를 탐색합니다. 깊이 방향으로 탐색하는 방식이므로, 스택이나 재귀를 사용하여 구현됩니다.
- BFS (Breadth-First Search, 너비 우선 탐색): 시작 노드에서부터 인접한 노드를 먼저 탐색한 후, 다시 그 인접 노드의 인접 노드들을 탐색하는 방식입니다. 주로 큐를 사용하여 구현됩니다.
⭐ DFS와 BFS의 차이점
| 특징 | DFS | BFS |
| 탐색 방식 | 깊이 우선, 한 경로를 끝까지 탐색 | 너비 우선, 인접한 노드를 모두 탐색 |
| 자료 구조 | 스택(재귀로 구현 가능) | 큐 |
| 경로 탐색 | 가능한 경로를 빠르게 찾음 | 최단 경로 탐색에 유리 |
| 메모리 사용량 | 재귀 호출에 따른 스택 메모리 사용 증가 | 큐에 노드 저장 공간 필요 |
| 대표적 사용 예시 | 백트래킹, 퍼즐 문제 | 최단 경로 찾기, 최단 이동 횟수 계산 |
⭐ DFS와 BFS의 기본 코드 구조
✅ DFS 기본 코드
import java.util.*;
public class GraphDFS {
private Map<Integer, List<Integer>> graph = new HashMap<>();
private Set<Integer> visited = new HashSet<>();
// 그래프에 노드와 간선을 추가하는 메서드
public void addEdge(int src, int dest) {
graph.putIfAbsent(src, new ArrayList<>());
graph.get(src).add(dest);
}
// DFS 구현 (재귀 사용)
public void dfs(int node) {
if (visited.contains(node)) return;
visited.add(node);
System.out.print(node + " ");
// 현재 노드와 연결된 모든 노드에 대해 DFS 재귀 호출
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfs(neighbor);
}
}
}
public static void main(String[] args) {
GraphDFS graphDFS = new GraphDFS();
graphDFS.addEdge(0, 1);
graphDFS.addEdge(0, 2);
graphDFS.addEdge(1, 2);
graphDFS.addEdge(2, 0);
graphDFS.addEdge(2, 3);
graphDFS.addEdge(3, 3);
System.out.println("DFS 탐색 결과:");
graphDFS.dfs(2);
}
}✅ BFS 기본 코드
import java.util.*;
public class GraphBFS {
private Map<Integer, List<Integer>> graph = new HashMap<>();
// 그래프에 노드와 간선을 추가하는 메서드
public void addEdge(int src, int dest) {
graph.putIfAbsent(src, new ArrayList<>());
graph.get(src).add(dest);
}
// BFS 구현 (큐 사용)
public void bfs(int startNode) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(startNode);
visited.add(startNode);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
// 현재 노드와 연결된 모든 노드를 큐에 추가
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
queue.add(neighbor);
visited.add(neighbor);
}
}
}
}
public static void main(String[] args) {
GraphBFS graphBFS = new GraphBFS();
graphBFS.addEdge(0, 1);
graphBFS.addEdge(0, 2);
graphBFS.addEdge(1, 2);
graphBFS.addEdge(2, 0);
graphBFS.addEdge(2, 3);
graphBFS.addEdge(3, 3);
System.out.println("BFS 탐색 결과:");
graphBFS.bfs(2);
}
}
⭐ DFS와 BFS 응용 방법
- DFS 응용
- 백트래킹: 퍼즐, 조합 및 순열 찾기 문제에서 모든 가능한 경우의 수를 탐색하는 데 사용합니다. 예를 들어, 미로 문제나 N-Queens 문제에서 특정 경로가 유효한지 확인하며 풀 수 있습니다.
- 연결 요소 찾기: 그래프의 각 연결 요소를 찾는 데 DFS를 사용하여, 하나의 DFS 탐색이 끝나면 연결 요소의 크기나 구성 요소를 기록할 수 있습니다.
- BFS 응용
- 최단 경로 찾기: 가중치가 없는 그래프에서 시작점에서 목표점까지의 최단 경로를 찾는 데 유용합니다. 예를 들어, 미로에서 출발점에서 도착점까지 가장 적은 이동 횟수로 이동할 때 BFS를 사용할 수 있습니다.
- 단계별 탐색 문제: 너비 우선 탐색은 단계별로 노드를 방문하므로, BFS는 특정 노드에서 일정 단계만큼 떨어진 노드를 찾는 문제에 적합합니다.
⭐ 예제 문제 및 응용 코드 예시
1️⃣ 미로 탐색 문제
- 문제: 미로의 시작점에서 출발해 목표점까지 이동하는데, 이동할 수 있는 최단 거리를 구합니다. BFS를 사용하여 미로를 탐색하고 이동 거리를 계산합니다.
import java.util.*;
class MazeSolver {
private static final int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우 이동
private static final int[] dy = {0, 0, -1, 1};
public int shortestPath(int[][] maze, int startX, int startY, int endX, int endY) {
int rows = maze.length;
int cols = maze[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[rows][cols];
queue.add(new int[]{startX, startY, 0});
visited[startX][startY] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1], dist = cell[2];
if (x == endX && y == endY) return dist;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && maze[nx][ny] == 0 && !visited[nx][ny]) {
queue.add(new int[]{nx, ny, dist + 1});
visited[nx][ny] = true;
}
}
}
return -1; // 목표 지점에 도달할 수 없는 경우
}
public static void main(String[] args) {
int[][] maze = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0}
};
MazeSolver solver = new MazeSolver();
System.out.println("최단 경로 길이: " + solver.shortestPath(maze, 0, 0, 4, 4));
}
}2️⃣ 모든 경로 탐색 문제
- 문제: 주어진 그래프에서 특정 시작점과 종료점 간 모든 가능한 경로를 찾습니다. 이 문제는 DFS로 풀 수 있으며, 백트래킹을 통해 경로를 저장합니다.
import java.util.*;
public class AllPathsDFS {
private Map<Integer, List<Integer>> graph = new HashMap<>();
// 그래프에 노드와 간선을 추가하는 메서드
public void addEdge(int src, int dest) {
graph.putIfAbsent(src, new ArrayList<>());
graph.get(src).add(dest);
}
// 모든 경로 찾기 - DFS 사용
public void findAllPaths(int start, int end, List<Integer> path, List<List<Integer>> allPaths) {
path.add(start);
if (start == end) {
allPaths.add(new ArrayList<>(path));
} else {
for (int neighbor : graph.getOrDefault(start, new ArrayList<>())) {
if (!path.contains(neighbor)) {
findAllPaths(neighbor, end, path, allPaths);
}
}
}
path.remove(path.size() - 1);
}
public static void main(String[] args) {
AllPathsDFS graph = new AllPathsDFS();
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
List<List<Integer>> allPaths = new ArrayList<>();
graph.findAllPaths(2, 3, new ArrayList<>(), allPaths);
System.out.println("모든 경로:");
for (List<Integer> path : allPaths) {
System.out.println(path);
}
}
}
🚩 결론
DFS와 BFS는 그래프 탐색의 핵심 알고리즘으로, 각자의 특징과 적합한 문제 유형을 이해하는 것이 중요합니다. 문제 상황에 따라 DFS나 BFS 중 적합한 알고리즘을 선택하여 효율적으로 문제를 해결해보는 연습을 해보시는 걸 추천드립니다!
코딩 테스트에서는 기본 구현뿐 아니라 이를 응용한 백트래킹, 최단 경로 탐색 등의 문제도 자주 출제되니 다양한 예제를 통해 충분히 연습해 보길 권장합니다!!