BOJ 11725번 트리의 부모 찾기

BOJ : https://www.acmicpc.net/problem/11725

GitHub : https://github.com/junho0956/Algorithm/blob/master/11725/11725/%EC%86%8C%EC%8A%A4.cpp

 

처음에는 입력이 번호 순서대로 주어지는 것인줄 알고 풀었다가 틀리고

그 다음에는 마구잡이가 된다는걸 알고 그냥 마구잡이로 아직 루트가 없는 노드는 큐에 넣어서

다시 확인하는 방법으로 풀었다가 시간초과가 나고.. 어려운 문제도 아닌데

앞으로는 좀 깔끔하게 정확하게 풀어가는 습관을 기를 수 있게 노력해야겠다;

 

마구잡이식으로 확인하면 무조건 시간초과가 뜨니

입력을 전부 받아놓고 루트부터 트리를 만들어가는 느낌으로 확인만 해주자

 

#include <iostream>
#include <vector>
using namespace std;
 
int arr[100001], v1, v2, N;
vector<int> v[100001];
 
void dfs(int num) {
 
    for (int i = 0; i < v[num].size(); i++) {
        if(!arr[v[num][i]]) arr[v[num][i]] = num, dfs(v[num][i]);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> v1 >> v2;
        v[v1].push_back(v2);
        v[v2].push_back(v1);
    }
 
    dfs(1);
    for (int i = 2; i <= N; i++)
        cout << arr[i] << '\n';
 
    return 0;
}