[백준] 11725 트리의 부모 찾기 c++

 

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

처음에는 DFS로 접근하지 않고 입력받을 때 조건에 따라 2차원 배열에 push_back하는 방법으로 풀었다.

2개의 테스트케이스를 통과했지만 제출하면 런타임오류(Out of Bounds)가 뜬다. 아무리봐도 배열 index에 문제가 없어보이는데.. 다시 찾아봐야겠다..

오답 Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int n;
vector<vector<int>> v;
int main()
{
    cin >> n;
    v.resize(n + 1);
    v[1].push_back(1);
    for (int i = 0; i < n - 1; i++) {
        int first, second;
        cin >> first >> second;
        //둘 중 하나가 1이면 v[~] = 1
        if (first == 1) {
            v[second].push_back(1);
            continue;
        }
        if (second == 1) {
            v[first].push_back(1);
            continue;
        }
        
        //이미 있다면 v[first] = second 혹은 v[second] = first
        if (v[first].size() != 0) { 
            v[second].push_back(first);
            continue;
        }
        if (v[second].size() != 0) {
            v[first].push_back(second);
            continue;
        }
    }
    for (int i = 2; i <= n; i++) {
        cout << v[i][0] << endl;
    }
}
 

KEY

• 1부터 시작해서 n개의 노드를 순회하면서, 먼저 방문하는 노드는 늦게 방문하는 노드의 부모가 된다.
• 답이 들어갈 2차원 배열(answer)을 따로 선언해서, answer[자식노드] = 부모노드를  저장하여 답을 출력했다.
• 답 출력 시 endl로 하면 시간초과가 뜨는 것을 주의하자.

 

정답 Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 100001;
int n;
vector<vector<int>> v;
vector<vector<int>> answer;
bool visited[MAX];
 
void dfs(int node) {
    for (int i = 0; i < v[node].size(); i++) {
        int next = v[node][i];
        if (visited[next])
            continue;
        
        answer[next].push_back(node);
        visited[next] = true;
        dfs(next);
    }
}
int main()
{
    cin >> n;
    v.resize(n + 1);
    answer.resize(n + 1);
    for (int i = 0; i < n-1; i++) {
        int first, second;
        cin >> first >> second;
        v[first].push_back(second);
        v[second].push_back(first);
    }
    visited[1] = true;
    dfs(1);
 
    for (int i = 2; i <= n; i++) {
        cout << answer[i][0] << "\n";
    }
}