오늘의 목표

1. DFS
2. BFS
3. DFS재귀

---

내용

DFS

DFS는 깊이 우선 탐색입니다. 스택을 이용하여 sibling보다 child를 우선시 하는 탐색 방법입니다. 예를 들어 이번차례에 노드A를 방문하였다면 다음차례는 동일한 부모를 둔 노드B보다 노드A의 자식 노드C가 우선순위를 가집니다. 그래프에서 본다면 해당경로를 끝까지 가본 다음 그 다음 경로를 끝까지 가보는 방식으로 해당 경로가 찾고자하는 경로와 반대 경로라면 많은 노드들을 탐색해야 할 수도 있습니다.

void DFS(){
	//첫 노드 결정
    //첫 노드를 스택에 삽입
    //첫 노드를 방문 표시
    //while(스택이 빌 때 까지)
    	//스택 pop
        //for(인접 노드 순차접근)
        	//if 조건만족 & 방문x 시
            	//방문 표시
                //스택 push
}

BFS

BFS는 너비 우선 탐색입니다. DFS와 대조적으로 큐를 이용합니다. 스택 사용시 형제 노드들을 push하더라도 해당노드에서 자식 노드들을 push한다면 자식노드들이 형제 노드들이 우선 방문됩니다. 하지만 큐 사용시 형제 노드들을 offer하면 자식 노드들을 offer하더라도 형제노드들이 먼저 방문되므로 우선순위에 있어 sibling > child입니다. 모든 경로를 가까운 거리부터 차례로 탐색하므로 거리가 가까우면 빠르게 찾을 수 있으나 거리가 멀면 모든 그래프를 탐색해야 할 수도 있습니다.

void BFS(){
	//첫 노드 결정
    //첫 노드 큐에 삽입
    //첫 노드 방문 표시
   	//while(큐가 빌 때 까지)
    	//큐 poll
        //for(인접 노드 순차 접근)
        	//if 조건 만족 & 방문x 시
            	//방문 표시
                //큐 offer
}

DFS 재귀 구현

DFS는 이전에 저장 해둔 형제들의 노드들보다 현재 새로 탐색한 노드의 자식들이 우선시 되므로 재귀적으로 구현이 가능합니다.
재귀구현에서 DFS에서 스택을 사용하지 않는다는 점, 매개변수로 추가적인 정보가 더 필요할 수 있다는 점이 다를 수 있으며 노드의 방문여부를 저장하는 점은 동일합니다.

void DFSR(노드){
	//방문 표시
    //for(인접 노드 순차 접근)
    	//if 조건 만족 & 방문x 시
        	//DFSR(인접 노드)
}

---

후기

학부생 시절 C++언어로 DFS와 BFS의 실행과정을 외우듯 외웠던 기억이 있습니다. 그렇게 외우던 기억이 있지만정작 실행과정은 기억에 잘 남지 않았지만, 이번에는 기준 없이 외우는것이 아닌 스택과 큐로 다르게 구현하는것을 이해 함으로써 명확히 이해한것 같습니다.

---

GitHub

https://github.com/ds02168/CodeStates/blob/main/src/JAVA_DataStructure/DFSBFSExample.java