백준 11725 - 트리의 부모 찾기 - DFS

문제

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

풀이전략

1. 트리의 루트는 1이다. 트리의 부모를 찾는 것이므로 당연히 DFS를 사용하는 것이 좋다.
2. 이 문제에서는 이진트리임을 밝히지 않았으므로 이진트리가 아닐수도 있다는 가정하에 계산한다.
3. N = 100,000 이므로 단순히 2D배열을 만들면 메모리제한에 걸린다. 따라서 vector의 배열을 이용하여 최대한 만드는 배열의 값을 줄인다.
4. 체크배열을 하나 만들어 DFS를 할때마다 이전 부모의 값을 저장해준다. 그렇게 하면 마지막에 체크배열만 출력하면 모든 노드들의 부모를 알 수 있게된다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
vector<int> a[100001];
int ans[100001];

void DFS(int v){

    for(int i=0; i<a[v].size(); i++){
    	// 부모가 없는 배열일 경우 DFS를 진행한다. 
        if(ans[a[v][i]] == 0){
        	// 부모를 저장해준다. 
            ans[a[v][i]] = v;
            DFS(a[v][i]);
        }
        
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    int ta, tb;
    for(int i=1; i<=N; i++){
        cin >> ta >> tb;
        a[ta].push_back(tb);
        a[tb].push_back(ta);
    }
    ans[1] = 1;
    DFS(1);
    //// endl을 써서 틀렸는데 '\n'을 써서 맞았다... 매우 중요함!
    for(int i=2; i<=N; i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

소감

이 문제를 해결할때 공간복잡도에 많이 신경을 써서 처리하기위해 벡터를 사용하였다. 하지만 이상한 부분에서 시간제한에 걸려버렸다. 그게 바로 endl이다. endl이 느리다는것을 이번에 알았기 때문에 10만개의 endl을 하면 시간복잡도에 걸린다는 것이다. 따라서 앞으로는 endl이 아니라 '\n'을 사용해야겠다.