생각정리/자료구조&알고리즘
[알고리즘] DFS / BFS (깊이 탐색 / 너비 탐색)
생각중임
2024. 2. 27. 20:03
그래프 탐색에서 각 정점을 지나가는 과정을 말하고 주로 사용되는 탐색 방법으로는 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search) 2가지 알고리즘이 있다.
깊이 우선 탐색 (Depth-First Search)
일반적으로 스택과 재귀함수로 구현을 하고 재귀함수가 편하고 많이 사용되고 있다.
탐색 과정
하나의 점에서 한쪽 방향(연결 노드)으로 먼저 이동을 하고 갈 수 있는 끝 점까지 탐색을 한 뒤 다시 시작 지점으로 돌아와 다른 방향으로 끝 점까지 탐색을 시도한다.
진행 중 여러 방향으로 연결된 점이 있다면 시작 점과 같이 한쪽 방향씩 끝 점을 탐색하고 시작 점으로 돌아와 결과를 출력한다.
경로 탐색
깊이 탐색에서 경로 탐색에 경우에는 갈림길이 있을 경우 때문에 우선순위 큐를 활용해서 재귀함수를 사용할 수 있다.
하지만 최적 경로의 경우에는 성능적으로 너비 탐색에 적합하여 깊이 탐색으로는 잘 풀지 않는다.
public class DepthFirstSearch {
public static void main(String[] args) {
int[][] map = {
{1, 1, 1, 1},
{1, 0, 0, 0},
{1, 1, 1, 1},
{1, 0, 0, 1}};
int cnt = 0;
Queue<Integer> queue = new PriorityQueue<>();
queue = dfs(queue, map, 0, 0, 1);
if (!queue.isEmpty()) cnt = queue.peek();
System.out.println(cnt);
}
private static Queue<Integer> dfs(Queue<Integer> queue, int[][] maps, int x, int y, int cnt) {
if (!queue.isEmpty() && queue.peek() < cnt) return queue;
if (x == maps.length-1 && y == maps[0].length-1) {
queue.offer(cnt);
return queue;
}
if (x >= 0 && y >= 0 && maps.length > x && maps[0].length > y && maps[x][y] != 0) {
maps[x][y] = 0;
dfs(queue, maps, x, y + 1, cnt + 1);
dfs(queue, maps, x + 1, y, cnt + 1);
dfs(queue, maps, x, y - 1, cnt + 1);
dfs(queue, maps, x - 1, y, cnt + 1);
maps[x][y] = 1;
return queue;
}
return queue;
}
}
범위 탐색
연결되어 있는 모든 지점들을 하나씩 헤아려
public class DepthFirstSearch {
public static void main(String[] args) {
int[][] map = {
{1, 1, 1, 1},
{1, 0, 0, 0},
{1, 1, 1, 1},
{1, 0, 0, 1}};
int cnt = 0;
cnt = dfs(0, 0, map);
System.out.println(cnt);
}
private static int dfs(int x, int y, int[][] map) {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int cnt = 1;
map[x][y] = 0;
for (int i = 0; i < dx.length; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if (nextX >= 0 && nextY >= 0 && nextX < map.length && nextY < map[0].length && map[nextX][nextY] == 1) {
cnt += dfs(nextX, nextY, map);
}
}
return cnt;
}
}
너비 우선 탐색(Breadth-Firsh Search)
일반적으로 큐를 이용해서 반복하는 구조로 구현을 하고 최단 경로를 찾는 다익스트라 알고리즘 등에 자주 사용된다.
탐색 과정
시작 점에서 움직일 수 있는 방향으로 모두 이동하고 해당 점들에서 다시 움직일 수 있는 방향으로 점차 움직인다.
한 점씩 이동을 하면서 갈 수 있는 끝 점까지 이동을 한 뒤 결과를 출력한다.
경로 탐색
최단 경로 탐색에 경우 여러 가지로 변형하여 너비 탐색 알고리즘이 주로 사용된다.
public class BreadthFirstSearch {
public static void main(String[] args) {
int[][] map = {
{1, 1, 1, 1},
{1, 0, 0, 0},
{1, 1, 1, 1},
{1, 0, 0, 1}};
int cnt = 0;
cnt = bfs(0, 0, map);
System.out.println(cnt);
}
private static int bfs(int x, int y, int[][] map) {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y, 1});
int[] cur = null;
while (!queue.isEmpty()) {
cur = queue.poll();
for (int i = 0; i < dx.length; i++) {
int nextX = cur[0] + dx[i];
int nextY = cur[1] + dy[i];
if (nextX >= 0 && nextY >= 0 && nextX < map.length && nextY < map[0].length && map[nextX][nextY] == 1) {
map[nextX][nextY] = 0;
queue.offer(new int[]{nextX, nextY, cur[2] + 1});
}
}
}
return cur[2];
}
}
범위 탐색
public class BreadthFirstSearch {
public static void main(String[] args) {
int[][] map = {
{1, 1, 1, 1},
{1, 0, 0, 0},
{1, 1, 1, 1},
{1, 0, 0, 1}};
int cnt = 0;
cnt = bfs(0, 0, map);
System.out.println(cnt);
}
private static int bfs(int x, int y, int[][] map) {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
map[x][y] = 0;
int cnt = 0;
while (!queue.isEmpty()) {
cnt++;
int[] cur = queue.poll();
for (int i = 0; i < dx.length; i++) {
int nextX = cur[0] + dx[i];
int nextY = cur[1] + dy[i];
if (nextX >= 0 && nextY >= 0 && nextX < map.length && nextY < map[0].length && map[nextX][nextY] == 1) {
map[nextX][nextY] = 0;
queue.offer(new int[]{nextX, nextY});
}
}
}
return cnt;
}
}
DFS / BFS (깊이 탐색 / 너비 탐색)에서 중요한 점
- 기본 형태는 대부분 동일한 구성으로 되지만 반복되는 범위와 조건들의 부여하는 방법을 찾아내는 게 주요 관점이다.
- 배열 혹은 수를 기준으로 하는 경우가 많다.
- 일반적으로 깊이 탐색은 현재 점을 기준으로 비교하고 너비 탐색은 다음 점을 기준으로 비교한다.
- 너비 탐색의 경우 지나간 지점을 반복하지 않도록 체크를 해주는 부분이 필요하다.
- 너비 탐색에서 큐에 담는 값은 횟수나 크기등 다양한 값이 필요할 경우가 있어 배열을 이용할 수도 있고 클래스를 만들어서 이용하는 경우도 많다.
- 깊이 탐색과 너비 탐색 중 어떤 알고리즘을 사용해야 적합할지를 모를 때는 먼저 너비 탐색을 고려해 보고 깊이 탐색을 고려해 보면 알고리즘을 생각하기 편했다. (개인적인 생각)