[알고리즘 / Java] 완전탐색(DFS, BFS)

- DFS(깊이 우선 탐색, Depth-First Search) : 루트노드나 다른 임의노드에서 다음 분기로 넘어가긴 전에,

해당 분기를 모두 탐색하는 방법으로 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색합니다.

1. 자기 자신을 호출하는 순환 알고리즘의 형태입니다. 
   -> 재귀나 스택을 이용 (컴퓨터 자체가 스택구조 이기때문에 재귀만으로 가능)
2. 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 받드시 검사해야합니다.
   (만약 검사하지 않을 경우 무한루프의 위험이 있습니다.)
   ex) visited[index] = true; // 방문
3. 미로탐색에서 해당 분기에서 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게되면 다시 가장
   가까운 갈림길(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사합니다.
4. 모든 노드를 방문하고자 할 때 사용합니다.
5. BFS(너비우선탐색)에 비해 구현이 간단합니다.
6. 반면 BFS에 비해 탐색속도가 느립니다.

public static void dfs(int node, boolean[] visited) {
	if(visited[node]) return;
    
    visited[node] = true;
    for(int nextNode : nodeList[node]) {	// nodeList: LinkedList(리스트에는 연결노드정보)
    	dfs(nextNode, visited);
    }
}

---

- BFS(너비 우선 탐색, Bread-First Search) : 루트노드나 다름 임의노드에서 시작한 인접노드를 먼저 탐색합니다.

1. 재귀적으로 동작하지 않습니다.
2. DFS와 마찬가지로 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야합니다.
3. 방문한 노드들을 차례대로 저장한 후 꺼낼 수 있는 큐를 사용합니다. (FIFO)
4. 시작 노드로부터 가까운 노드(깊이가 같은)를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문합니다.
5. 두 노드 사이의 최단 경로나 임의의 경로를 찾을 때 사용합니다.
   (DFS를 사용하면 모든 경로를 다 탐색해야 할 수도 있지만, BFS는 찾고자하는 노드 주변부터 순회
   하기 때문에 효율적입니다.)

public static void dfs(int node, boolean[] visited) {
	Queue<Integer> queue = new LinkedList<Integer>();
    queue.offer(node);
    
    while(!queue.isEmpty()) {
    	node = queue.poll();
        
        if(visited[node]) continue;
        visited[node] = true;
        
        for(int nextNode : nodeList[node]) {
        	queue.add(nextNode);
        }
    }
}