DFS와 BFS

1. DFS

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
노드와 간선을 표현하기위해 인접행렬과 인접리스트방식을 사용한다.
인접행렬 : 2차원 배열로 그래프의 연결관계를 표현
인접리스트 : 리스트로 그래프의 연결관계를 표현

동작과정
1. 탐색시작 노드를 스택에 넣고 방문처리를 한다.
2. 탐색시작 노드와 인접한 노드 중 방문처리를 하지 않은 노드가 있다면 방문처리를 하고 스택에 넣는다. 방문하지 않은 인접노드가 없다면 스택의 최상단 노드를 꺼낸다.

2. BFS

너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 탐색하는 알고리즘이다.
큐를 사용해서 구현하며 먼저 탐색한 노드가 먼저 나오게 된다.

동작과정
1. 탐색시작 노드를 큐에 넣고 방문처리를 한다.
2. 인접노드 중 탐색하지 않은 노드가 있다면 방문처리를 하고 큐에 모두 삽입한다.

3. DFS, BFS의 비교

			DFS 		BFS
	동작원리	       스택		큐
	구현방법	     재귀함수	  큐 자료구조를 이용

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

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

public class Main {

	static ArrayList<Integer>[] list;
	static int start;
	static boolean[] bln;
	static Queue<Integer> q;
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		// 정점의 수
		int n = sc.nextInt();
		// 간선의 수
		int m = sc.nextInt();
		// 탐색의 시작점
		start = sc.nextInt();
		
		list = new ArrayList[n+1];
		// 각 정점을 방문처리할 배열
		bln = new boolean[n+1];
		// 그래프 초기화
		for(int i=1; i<=n; i++) {
			list[i] = new ArrayList<Integer>();
		}
		// list에 노드와 간선정보를 저장한다.
		for(int i=1; i<=m; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			list[u].add(v);
			list[v].add(u);
		}
		for(int i=1; i<=n; i++) {
			Collections.sort(list[i]);
		}
		
		bfs(start);
		System.out.println();
		bln = new boolean[n+1];
		dfs(start);
	}
	
	static void bfs(int n) {
		// 해당 노드를 방문 했다면 함수를 종료한다.
		if(bln[n]) return;
		// 노드를 방문처리를 해준다.
		bln[n] = true;
		System.out.print(n+" ");
		for(int y : list[n]) {
			if(!bln[y])	bfs(y);
		}
	}
	
	static void dfs(int n) {
		q = new LinkedList<Integer>();
		q.add(n);
		bln[n] = true;
		
		while(!q.isEmpty()) {
			int x = q.poll();
			System.out.print(x+" ");
			for(int y : list[x]) {
				if(!bln[y]) {
					bln[y] = true;
					q.add(y);
				}
			}
		}	
	}

}