[C++]백준 15805번 트리 나라 관광 가이드

📌문제 링크

---

https://www.acmicpc.net/problem/15805

📌문제 설명

---

문제를 풀이하며 아쉬움이 많이 남는 문제였다. 전위 순회의 개념을 떠올렸으면 더 효율적으로 문제풀이를 할 수 있었다. 주어진 탐색 순서를 바탕으로 트리를 재구성한 후 dfs탐색으로 노드의 부모를 출력했다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v[200001];
int visited[200001];
int N, node, start;   

void input(){
    cin >> N >> start;
    int prev = start;
    for(int i = 0; i < N-1; i++){
        cin >> node;
        if(i == 0){
            v[start].push_back(node);
            v[node].push_back(start);
        }
        else{
            v[node].push_back(prev);
            v[prev].push_back(node);
        }
        prev = node;
    }
}

void dfs(int idx, int prev){
    visited[idx] = prev;
    for(auto it : v[idx]){
        if(visited[it] == -1){
            dfs(it, idx);
        }
    }
}

void init(){
    for(int i = 0; i <= N; i++){
        visited[i] = -1;
    }
}

void solve(){
    input();
    init();
    dfs(start, -1);
    int cnt;
    for(int i = 0; i <= N; i++){
        if(i != 0 && visited[i] == -1){
            cnt = i;
            break;
        }
    }
    cout << cnt<< "\n";
    visited[start] = -1;
    for(int i = 0; i <= cnt - 1; i++){
        cout << visited[i] << " ";
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}