백준 11725번 트리의 부모 찾기

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

DFS를 통해 노드의 부모를 찾는 문제였습니다.

주어진 노드들이 부모 - 자식 순서가 아니라 랜덤으로 주어지기 때문에 양방향으로 넣어줘야합니다.

1은 무조건 루트이기 때문에 1부터 넣고 방문했다고 표시한 뒤 전형적인 DFS를 진행해주면 됩니다.

#include <iostream>

#include <vector>

using namespace std;

 

const int MAX = 100000 + 1;

 

int N;

bool visited[MAX];

int parent[MAX];

vector<int> tree[MAX];

 

void findParent(int nodeNum)

{

        visited[nodeNum] = true; //방문한 노드 표시

 

        //DFS

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

        {

                 int next = tree[nodeNum][i];

 

                 if (!visited[next])

                 {

                         parent[next] = nodeNum; //next의 parent는 nodeNum

                         findParent(next);

                 }

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

 

        cin >> N;

 

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

        {

                 int node1, node2;

                 cin >> node1 >> node2;

 

                 tree[node1].push_back(node2);

                 tree[node2].push_back(node1);

        }

 

        findParent(1); //root부터

 

        //endl 사용 시 시간 초과

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

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

 

        return 0;

}

개발환경:Visual Studio 2017

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