그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.
📌여기서 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다.
1. 깊이 우선 탐색 (DFS, Depth-First Search)
: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
💡 깊이 우선 탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에
해당 분기를 완벽하게 탐색하는 방식을 말합니다.
예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가
더 이상 갈 수 없게 되면 다시 왔던 길로 돌아와서
다른 갈림길이 존재하는 곳에서 부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다.
1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
2. 너비 우선 탐색 (BFS, Breadth-First Search)
: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
너비 우선 탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.
* 깊이 우선 탐색의 경우 - 모든 경로를 다 살펴봐야 함
* 너비 우선 탐색의 경우 - 시작 정점으로 부터 최단 거리 검색 가능
3. 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 비교
| DFS(깊이우선탐색) | BFS(너비우선탐색) |
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
💡DFS와 BFS의 시간복잡도
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일합니다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.
3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용
DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제 (DFS, BFS 모두 사용 가능)
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다.
2) 경로의 특징을 저장해둬야 하는 문제 (DFS 사용이 효율적)
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
3) 최단거리 구해야 하는 문제 (BFS 사용이 효율적)
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.
이밖에도
- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
4. DFS와 BFS을 사용한 JAVA코드
DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데,
첫 번째로 스택을 이용하는 것
두 번째로 재귀함수를재귀 함수를 이용하는 것인데, 재귀 함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다.
재귀 함수란 함수 내부에서 함수가 자기 자신을 또다시 호출하는 함수를 의미합니다.
이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되기 때문에
함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다.
[JAVA] 백준 2667번: 단지번호붙이기 ( 초급 2-39 ) 문제 참고
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class baekjoon2667_2 {
private static int n;
private static int count;
private static int[][] info;
private static boolean[][] visit;
private static int result = 0;
private static ArrayList<Integer> resultList = new ArrayList<>();
private static int[] rowTemp = { -1, 1, 0, 0 };
private static int[] colTemp = { 0, 0, -1, 1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
info = new int[n][n];
visit = new boolean[n][n];
for (int i = 0; i < n; i++) {
String temp = br.readLine();
for (int j = 0; j < n; j++) {
info[i][j] = Character.getNumericValue(temp.charAt(j));
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 방문한 적이 없는 (!visit[i][j]) 집이 있는 곳 (info[i][j] != 0) 을 모두 확인
if (!visit[i][j] && info[i][j] != 0) {
// count는 단지 내 집의 수를 의미
count = 1;
// resultList에는 단지 내 집의 수를 저장.
resultList.add(count);
// 현재 집과 인접한 집을 모두 검색 (단지 내 모든 집 구하기)
dfs2667(i, j);
// 단지 수 ++;
result++;
}
}
}
// 총 단지수 출력
System.out.println(result);
// 오름 차순 정렬
Collections.sort(resultList);
// 단지 내 집의 수를 오름차순으로 출력
resultList.forEach(System.out::println);
}
private static void dfs2667(int row, int col) {
visit[row][col] = true;
resultList.set(result, count);
// 집의 수 ++;
count++;
int nextRow;
int nextCol;
// 현재 집의 위치에서 상, 하, 좌, 우에 위치한 모든 집을 방문
for (int i = 0; i < 4; i++) {
nextRow = row + rowTemp[i];
nextCol = col + colTemp[i];
// 방문하려는 집의 위치가 범위 내에 존재하여야 하며
if (nextRow >= 0 && nextCol >= 0 && nextRow < n && nextCol < n) {
// 방문 하려는 집은 이전에 방문한 적이 없었어야 하며, 집이 있는 곳이어야 한다.
if (!visit[nextRow][nextCol] && info[nextRow][nextCol] != 0) {
dfs2667(nextRow, nextCol);
}
}
}
}
}
BFS 알고리즘은 큐(Queue)를 사용해서 문제를 해결하면 됩니다.
BFS 알고리즘을 사용할 때 주의점은 방문 여부 변경하는 지점을 큐에 넣을 때 진행하여야 한다는 점입니다.
큐에서 꺼낼 때 방문 여부를 변경한다면, 똑같은 지점을 두번 큐에 넣기 때문에 메모리 초과가 발생할 수 있습니다.
[JAVA] 백준 2178번: 미로 탐색 ( 초급 2-41 ) 참고
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class baekjoon2718 {
private static int targetRow;
private static int targetCol;
private static int[] rowTemp = { -1, 1, 0, 0 };
private static int[] colTemp = { 0, 0, -1, 1 };
private static int[][] info;
private static boolean[][] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
targetRow = Integer.parseInt(st.nextToken());
targetCol = Integer.parseInt(st.nextToken());
// 미로 정보를 담을 공간 초기화
info = new int[targetRow][targetCol];
// 방문 여부 확인
visit = new boolean[targetRow][targetCol];
// 미로 정보 저장
for (int i = 0; i < targetRow; i++) {
String temp = br.readLine();
for (int j = 0; j < targetCol; j++) {
info[i][j] = Character.getNumericValue(temp.charAt(j));
}
}
bfs2718();
}
private static void bfs2718() {
Queue<Maze> queue = new LinkedList<>();
queue.add(new Maze(0, 0, 1));
visit[0][0] = true;
int row;
int col;
int count;
int nextRow;
int nextCol;
while (!queue.isEmpty()) {
Maze maze = queue.remove();
row = maze.height;
col = maze.width;
count = maze.count;
if (row == targetRow - 1 && col == targetCol - 1) {
System.out.println(count);
System.exit(0);
}
for (int i = 0; i < 4; i++) {
nextRow = row + rowTemp[i];
nextCol = col + colTemp[i];
if (nextRow >= 0 && nextCol >= 0 && nextRow < targetRow && nextCol < targetCol) {
if (info[nextRow][nextCol] != 0 && !visit[nextRow][nextCol]) {
visit[nextRow][nextCol] = true;
queue.add(new Maze(nextRow, nextCol, count + 1));
}
}
}
}
}
}
class Maze {
int height;
int width;
int count;
Maze(int height, int width, int count) {
this.height = height;
this.width = width;
this.count = count;
}
}