[BOJ알고리즘, C++]#1068_트리, 그래프 탐색, 완전 탐색, 깊이 우선 탐색, DFS

 

#1. 문제

1068번: 트리

 

---

 

#2. 풀이

 

1. 깊이 우선 탐색

[자료구조]#6_그래프

 

[정의] : 깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 알고리즘입니다. 깊이 우선 탐색은 임의의 출발 정점으로부터 더 이상 확장할 수 없는 단말 노드까지 우선적으로 탐색을 진행하여, 최종적으로 그래프의 모든 노드를 탐색합니다. 깊이 우선 탐색의 구현 방법은 재귀 호출을 활용하는 방법과 스택 자료구조를 활용하는 방법이 있습니다.

 

2. 루트 노드를 찾고, 루트 노드를 시작으로 DFS를 수행하며 단말 노드를 찾자

1. 먼저, 루트 노드를 찾습니다. 루트 노드는 부모 노드가 없고 자식 노드만 있는 노드입니다.
2. 삭제할 노드의 방문 여부를 참으로 초기화합니다.
3. 루트 노드를 시작으로 깊이 우선 탐색을 수행하고, 현재 정점이 자식 노드를 가질 경우 '단말 노드'가 아님을 확인하고 다시, 탐색을 계속 진행합니다.
4. 깊이 우선 탐색 진행 중 '방문한 노드(삭제 노드)'를 만나면 탐색을 중단하며, 이를 통해 삭제 노드의 하위 레벨에 연결되어 있는 노드들에 대한 탐색을 진행하지 않게 합니다.

 

---

 

#3. 코드

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int N, rootIdx, deleteNode, leaves;
vector<int> tree;
vector<bool> visited;

void dfs(int node)
{
    bool IsLeaf = true;
    visited[rootIdx] = true;
    for (int i = 0; i < N; ++i)
    {
        if (!visited[i] && tree[i] == node)
        {
            IsLeaf = false;
            dfs(i);
        }
    }
    if (IsLeaf)
        leaves++;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    tree.resize(N);
    visited.resize(N, false);

    for (int i = 0; i < N; ++i)
    {
        cin >> tree[i];
        if (tree[i] == -1)
            rootIdx = i;
    }

    cin >> deleteNode;
    visited[deleteNode] = true;

    if (deleteNode != rootIdx)
    {
        dfs(rootIdx);
    }

    cout << leaves;

    return 0;
}

 

---