[Algorithm] Baekjoon 11725번 : 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

vector<int> v[100001];
bool visited[100001];
int result[100001];
 
 
void recur(int n)
{
    visited[n] = true;
 
    for (int i = 0; i < v[n].size(); i++)
    {
        int next = v[n][i];
 
        if (!visited[next])
        {
            result[next] = n;
            recur(next);
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int input1 = 0;
    int input2 = 0;
 
    cin >> n;
 
    for (int i = 0; i < n-1; i++)
    {
        cin >> input1 >> input2;
        v[input1].push_back(input2);
        v[input2].push_back(input1); 
    }
 
    recur(1);
    
    for (int i = 2; i <= n; i++)
    {
        printf("%d\n", result[i]);
    }
}

무난한 dfs로 푼 코드인데, 저기서 printf를 cout으로 하면 시간초과가 뜬다.

반드시 백준에서 풀때는 cout대신 printf를 사용하도록 하자.

 

문제자체는 dfs의 성질을 이용해서 푸는 문젠데 솔직히 나는 보자마자 바로 코드가 떠오르지 않았다.

개인적인 생각이지만 이정도는 바로 생각이 났어야 했는데.. 아직도 dfs든 bfs든, 문제를 훨씬 더 많이 풀어봐야할 것 같다.