<aside> ❓ DFS는 Depth First Search의 약자로 깊이 우선 탐색을 말하고, BFS는 Breath First Search의 약자로 너비 우선 탐색을 말한다.

</aside>

→ 스택(Stack), 큐(Queue), 재귀(Recursive)를 이용

위의 그림처럼 탐색을 위한 node는 다음과 같이 정의될 수 있다.

class Node {
	int data;
	Node lt, rt;
	
	/* 생성자 */
	public Node(int val) {
		data = val;
		lt = null;
		rt = null;
	}
}

DFS(Depth First Search)

• DFS는 자기 자신을 호출하는 ‘순환 알고리즘’ 형태 (VLR traversal)

• 0 → 1 → 3 → 1 → 4 (BackTracking)

  

• 일반적으로 스택(Stack)을 사용하고 모든 노드를 방문하고자 할 때 사용한다.

• BFS보다 간단하게 구현 가능하지만 검색 속도가 느리다.

public void DFS(Node root) {
	if(root == null) return;
	else {
		System.out.print(root.data + " ");
		DFS(root.lt);
		DFS(root.rt);
	}
}
// 결과: 0 1 3 4 2 5 6

BFS(Breath First Search)

• BFS는 방문한 노드들을 차례대로 커낼 수 있는 큐(Queue)를 사용한다.

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하기 때문에 대게 두 노드 사이의 최단 경로를 찾을 때 주로 사용한다.

  

public void BFS(Node root) {
	Queue<Node> q = new LinkedList<>();
	
	q.offer(root);
	int L = 0; // Level
	
	while(!q.isEmpty()) {
		int len = q.size();
		System.out.println(L + " : ");
		
		for(int i=0; i<len; i++) {
			Node current = q.poll();
			System.out.println(current.data + " ");
			if(current.lt != null) {
				q.offer(current.lt);
			}
			if(current.rt != null) {
				q.offer(current.rt);
			}
		}
		
		L++;
		System.out.println();
	}
}
// 0 : 0
// 1 : 1 2
// 2 : 3 4 5 6

⭐DFS/BFS in Programmers

프로그래머스에 있는 DFS/BFS 문제들

타켓 넘버