[BOJ알고리즘, C++]#11725_트리의 부모 찾기, 트리 탐색

 

[BOJ알고리즘, C++]#11725_트리의 부모 찾기

 

BOJ 알고리즘 문제 풀이, 11725번 문제 트리의 부모 찾기

트리의 탐색 방법에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#0. 문제

 

 

#1. 풀이

1. 트리 자료구조

[자료구조]#5_트리

 

• 트리는 1:N 관계의 비 선형 연결 자료구조입니다.
• 트리는 노드와 간선으로 구성되어, 각 노드 사이의 연결 관계는 간선으로 표현합니다.
• 트리 자료구조와 그래프 자료구조의 탐색 방법은 일반적으로 "DFS(깊이 우선 탐색)"과 "BFS(너비 우선 탐색)"가 있습니다.

 

2. 트리 vs 그래프

1. 계층 구조 : 트리는 계층적 구조를 가진 노드들의 집합이며, 그래프는 노드들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조입니다.
2. 순환 여부 : 트리는 그래프의 특별한 형태로 볼 수 있습니다. 트리는 하나의 연결된 컴포넌트이며, 순환이 없는(acyclic) 그래프입니다. 하지만, 그래프는 순환이 존재할 수 있습니다.
3. 루트 노드 : 트리는 계층 구조의 가장 상위 계층인 "루트 노드"가 있으며, 그래프에는 루트 노드의 개념이 없습니다.
4. 간선 개수 : 만약 트리의 노드 개수가 N개 일 때, 간선의 개수는 항상 N-1개입니다. 하지만, 그래프의 정점 개수가 N개 일 때, 간선의 개수는 항상 N-1개가 아닙니다. 즉, 트리는 두 노드 사이에 하나의 경로만 존재하며, 그래프는 그렇지 않을 수 있습니다.
5. 부모-자식 관계 : 트리의 각 노드는 최대 하나의 부모 노드를 가지며, 그래프는 부모-노드 자식 관계 개념이 없습니다.

 

3. 트리 탐색

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

 

• 트리 자료구조의 탐색 방법은 두 가지입니다.
• 먼저, DFS(깊이 우선 탐색)는 시작 노드부터 시작해 더 이상 확장할 수 없는 단말 노드까지 한 깊이로 먼저 탐색을 진행하고, 이전 단계로 돌아와 미탐색 인접 노드들을 차례대로 탐색하는 방법입니다. DFS를 구현하는 방법은 두 가지입니다. (1) 방문 여부 체크 및 재귀 호출 활용, 그리고 (2) 방문 여부 체크 및 스택 자료구조 활용이 있습니다.
• 다음으로, BFS(너비 우선 탐색)은 시작 노드부터 시작해 해당 레벨의 인접 정점들을 모두 탐색하고 다음 레벨의 노드로 순차적으로 이동하며 탐색하는 방법입니다. BFS의 구현은 방문 여부 체크 및 큐 자료구조를 활용합니다.

 

#2. 코드

1. 코드

// #1. DFS(재귀 호출) 활용 방법
#include <iostream>
#include <vector>
using namespace std;

vector<int> graph[100001];
int ans[100001];
bool visited[100001] = {0,};

void DFS(int start)
{
    visited[start] = true;
    for(int i=0; i<graph[start].size(); i++)
    {
        int neighbor = graph[start][i];
        if(!visited[neighbor])
        {
            ans[neighbor] = start;
            DFS(neighbor);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N;
    
    cin >> N;
    
    for(int i=1; i<=N; i++)
    {
        int x,y;
        cin >> x;
        cin >> y;
        
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    
    DFS(1);
    
    for(int i=2; i<=N; i++)
    {
        cout << ans[i] << '\n';
    }
    
}

// #2. DFS(스택) 활용 방법
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> graph[100001];
int ans[100001];
bool visited[100001] = {0,};

void DFS(int start)
{
    stack<int> s;
    visited[100001] = {0,};
    
    s.push(start);
    visited[start] = true;
    
    while(!s.empty())
    {
        int cur = s.top();
        s.pop();
        for(const auto& next : graph[cur])
        {
            if(!visited[next])
            {
                visited[next] = true;
                ans[next] = cur;
                s.push(next);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N;
    
    cin >> N;
    
    for(int i=1; i<=N; i++)
    {
        int x,y;
        cin >> x;
        cin >> y;
        
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    
    DFS(1);
    
    for(int i=2; i<=N; i++)
    {
        cout << ans[i] << '\n';
    }
    
}

// #3. BFS(큐) 활용 방법
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> graph[100001];
int ans[100001];

void BFS(int start)
{
    queue<int> q;
    bool visited[100001] = {0,};
    
    q.push(start);
    visited[start] = true;
    
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for(const auto& neighbor : graph[cur])
        {
            if(!visited[neighbor])
            {
                visited[neighbor] = true;
                ans[neighbor] = cur;
                q.push(neighbor);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N;
    cin >> N;
    
    for(int i=1; i<=N; i++)
    {
        int from, to;
        cin >> from;
        cin >> to;
        
        graph[to].push_back(from);
        graph[from].push_back(to);
    }
    
    BFS(1);
    
    for(int i=2; i<=N; i++)
        cout << ans[i] << '\n';
}