깊이 우선 탐색 (DFS)

개념

• 루트 노드에서 시작해서 다음 branch로 넘어가기 전에 해당 분기를 완벽하게 탐색 → 모든 노드를 방문하고자 하는 경우 선택

• 스택(Stack) 사용 : LIFO

풀이

1. 시작노드 (Start Node) 스택에 삽입 + 방문처리

2. 1. 스택의 최상단 노드 확인
   • 최상단 노드가 방문하지 않은 인접 노드 有 → 그 노드 스택에 삽입 및 방문 처리
   • 최상단 노드가 방문하지 않은 인접 노드 無 → 스택에서 최상단 노드 뺌

코드

void dfs(int now, int *checked) {
    // 시작노드 방문처리
    if(checked[now]) return;
    checked[now] = true;
    cout << now << " ";
    for(int i=0;i<adj[now].size();i++) {
        int adjNode = adj[now][i];
        dfs(adjNode, checked);
    }
}