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

문제링크 : https://www.acmicpc.net/problem/15805

15805번: 트리 나라 관광 가이드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321; 

int N;
int arr[200001];
int parent[200001];
vector<int>v;
int visited[200001];

set<int>t;

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

    cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];

    parent[arr[0]]=-1; //루트노드
    v.push_back(arr[0]); //트리에 넣기
    visited[arr[0]]=1; //방문처리

    for(int i=1; i<N; i++)
    {
        if(visited[arr[i]]) continue; //중복 제거
        parent[arr[i]] = arr[i-1]; //부모 연결
        visited[arr[i]]=1; //방문처리
        v.push_back(arr[i]); //트리에 넣기
    }

    cout << v.size() << "\n";
    for(int i=0; i<v.size(); i++) cout << parent[i] << " ";

    return 0;
}

 

입력받은 값의 순서는 방문한 순서이기에 첫 값은 루트노드이다.

따라서 해당 값은 -1 및 방문처리를 우선하고 i=1부터 탐색을 시작한다.

 

해당 인덱스에 해당하는 값이 중복되지 않은 값이라면 부모 연결을 해주고 트리에 넣어준다.

중복되지 않은 값의 경우 그대로 트리에 부모 자식간으로 연결되므로 부모의 값은 직전값이 된다.

만약 중복된 경우라면 이미 처음에 방문했던 부모로 다시 올라갔다가 다른 값으로 탐색을 시작하는 경우이다.

 

중복체크를 위해 visited배열을 사용했으나 set을 사용하는게 더 깔끔하게 풀이가 가능했을 것 같다.