[알고리즘] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

DFS (깊이 우선 탐색) 알고리즘

말 그대로 그래프를 깊숙이 탐색하는 알고리즘이다.

DFS는 Stack 또는 재귀 함수를 통해 구현한다.

 

DFS 알고리즘은 최소, 최단 탐색이 보장되지 않으며

모든 경로를 찾아봐야 하는 경우에 사용하는 것이 좋다.

---

BFS (너비 우선 탐색) 알고리즘

DFS와 달리 시작 정점 방문 후 인접한 모든 정접을 먼저 탐색하는 알고리즘이다.

BFS는 Queue를 통해 구현한다.

 

BFS 알고리즘은 최소, 최단 탐색이 보장되며

DFS로 풀 수 있는 문제는 BFS로도 풀 수 있다 (아마도? 효율보장 X)

---

DFS와 BFS 기본 코드

백준 1260번 문제를 풀이한 것이다.

https://www.acmicpc.net/problem/1260

DFS와 BFS의 기본코드로

문제풀이 시 기본코드로 뼈대를 만들고 제약 조건에 따라 수정하면 된다!

 

⭐여기서 중요한 점은 연결설정과 방문여부를 체크해 주는 것

import java.io.*;
import java.util.*;

public class P1260 {
	static StringBuilder sb = new StringBuilder();
	static int n; // 정점의 개수
	static int m; // 간선의 개수
	static int v; // 탐색을 시작할 정점의 번호
	static int[][] map; // 그래프
	static boolean[] visited; // 방문여부 체크
	
	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());
		m = Integer.parseInt(st.nextToken());
		v = Integer.parseInt(st.nextToken());
		
		map = new int[n+1][n+1];
		visited = new boolean[n+1];
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			map[x][y] = map[y][x] = 1;
		}
		
		dfs(v);
		sb.append("\n");
		visited = new boolean[n+1];
		bfs(v);
		System.out.println(sb);
	}
	
	static void dfs(int node) {
		visited[node] = true;
		sb.append(node + " ");
		for(int i=1; i<n+1; i++) {
			if(map[node][i]==1 && !visited[i]) {
				dfs(i);
			}
		}
	}
	static void bfs(int node) {
		visited[node] = true;
		Queue<Integer> q = new LinkedList<>();
		q.add(node);
		while(!q.isEmpty()) {
			int x = q.poll();
			sb.append(x + " ");
			for(int i=1; i<n+1; i++) {
				if(map[x][i]==1 && !visited[i]) {
					q.add(i);
					visited[i] = true;
				}
			}
		}
	}
}