dfs를 이용한 노드 탐색

출처 : 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

* 작성 이유

▶ dfs에 대해 문제들을 풀어봤으나 일부는 블로그에 남기는 것이 좋을 것 같아 작성함
▶ 일부 응용 전 개념만 적을 것이며, 유료 강의 내용이므로 특정 문제는 적지 않음

문제1

1에서 2, 3, 4 탐색 시 노드의 개수는?

문제1 코드

▶ vector 사용

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1004];
int visited[1004];
int dfs(int here) {
    int ret = 1;
    for(int there : adj[here]) {
        if(visited[there]) continue;
        ret += dfs(there);
    }
    return ret;
}
int main() {
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[1].push_back(4);
    visited[1] = 1;
    cout << dfs(1) << '\n';
    return 0;
}

문제2

리프노드 : 자식의 개수가 0인 노드
리프노드의 개수는? (빨강색 원으로 표시한 것, 총 3개가 나와야 함)

문제2 코드

#include <bits/stdc++.h>
using namespace std;
int n, m, r;
vector<int> adj[1004];
int dfs(int here) {
    int ret = 0;
    int child = 0;
    for(int there : adj[here]) {
        ret += dfs(there);
        child++;
    }
    if(child == 0) return 1;
    return ret;
}
int main() {
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[2].push_back(5);
    
    cout << dfs(1) << '\n';
    return 0;
}