백준 15805번 트리 나라 관광 가이드

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

전위 순회 탐색을 생각해보면 쉽게 풀 수 있는 문제였습니다.

한번도 방문하지 않은 노드는 (해당 노드가 등장하기 전 노드)의 자식입니다.

#include <iostream>

#include <set>

using namespace std;

 

const int MAX = 200000 + 1;

 

int A[MAX];

int parent[MAX];

set<int> tree;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> A[i];

 

        parent[A[0]] = -1;

        tree.insert(A[0]);

        for (int i = 1; i < N; i++)

        {

                 //여태까지 등장하지 않았다면

                 if (!tree.count(A[i]))

                 {

                         parent[A[i]] = A[i - 1];

                         tree.insert(A[i]);

                 }

        }

 

        cout << tree.size() << "\n";

        for (int i = 0; i < tree.size(); i++)

                 cout << parent[i] << " ";

        cout << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~