[알고리즘] DFS, BFS 구현 (백준)

BFS, DFS 둘다 모두 그래프를 탐색하는 방법이다.

 

DFS 깊이 우선 탐색 (Depth-First Search)

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.

2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.

3. 검색 속도 자체는 너비 우선 탐색에 비해서 느리다.

 

BFS 너비 우선 탐색 (Breadth-First Search)

1. 주로 최단 경로를 찾고 싶을 때 이 방법을 사용한다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
	static int[][] check; //간선 상태 확인
	static boolean [] visit; //방문여부
	static int n; //정점의 개수
	static int m; //간선의 개수
	static int start; //시작정점
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		start = sc.nextInt();
		
		check = new int [1001][1001];
		visit = new boolean [1001];
		
		for(int i=0; i<m; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			
			check[x][y] = check[y][x] = 1;
		}
		
		dfs(start);
		
		visit = new boolean [1001];
		System.out.println();
		
		bfs();
		
	}
	//dfs 구현
	public static void dfs(int i) {
		visit[i] = true;
		System.out.print(i + " ");
		
		for(int j = 1; j <= n; j++) {
			if(check[i][j] == 1 && visit[j] == false) {
				dfs(j);
			}
		}
	}
	
	//bfs구현
	public static void bfs() {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);
		visit[start] = true;
		System.out.print(start + " ");
		
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			
			for(int j=1; j<=n; j++) {
				if(check[temp][j] == 1 && visit[j] == false) {
					queue.offer(j);
					visit[j] = true;
					System.out.print(j + " ");
				}
			}
		}
	}
}