[C++] 백준 온라인 저지 11725번 트리의 부모 찾기 풀이

트리에 있는 노드들의 부모 노드를 찾아서 출력하는 문제

 

---

 

문제의 조건

 

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

 

풀이 과정

 

 양방향 그래프를 구성한 뒤 DFS로 풀었습니다. 

 

1. 2차원 배열을 만들고 입력 받으면서 양방향 그래프를 구성한다. 

 

2. 각 정점의 부모 노드를 저장할 1차원 배열을 만든다. 각 정점 인덱스에 부모 노드 번호를 저장할 것이라서 정점 갯수+1 크기로 만든다. 

 

3. 1번 정점부터 DFS로 그래프를 탐색하는데 현재 탐색중인 정점과 이웃한 정점을 아직 방문하지 않았다면 이웃 정점의 부모를 현재 정점으로 저장한다. 방문했으면 넘어간다. 

 

4. 마지막으로 2번에서 만든 배열을 2번 인덱스부터 순회하면서 원소를 출력한다. 이 때 endl을 쓰면 flush까지 같이 하다 보니 많이 느리다... "\n"을 쓰는 것이 좋다. (endl 쓰고 시간 초과 났는데 "\n"로만 바꿔주니까 바로 통과했슴다...)

 

 

코드

 

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    vector<vector<int>> vertex(N + 1);
    for (int i = 0; N - 1 > i; i++)
    {
        int a, b;
        cin >> a >> b;
        vertex[a].emplace_back(b); //양방향 그래프 구성 
        vertex[b].emplace_back(a);
    }
    
    vector<int> vertexPairs(N + 1);
    vector<bool> visited(N + 1, false);
    stack<int> s;
    s.emplace(1);
    visited[1] = true;
    while (!s.empty())
    {
        int cur = s.top();
        s.pop();
        
        //현재 정점과 연결된 정점들을 탐색한다. 
        for (int i = 0; vertex[cur].size() > i; i++)
        {
            int neighbor = vertex[cur][i];
            //방문하지 않은 정점이면 현재 정점을 neighbor의 부모 노드로 저장한다. 
            if (!visited[neighbor])
            {
                s.emplace(neighbor);
                visited[neighbor] = true;
                vertexPairs[neighbor] = cur;
            }
        }
    }
    
    //시간초과 방지를 위해 "\n"을 쓰자...!!
    for (int i = 2; vertexPairs.size() > i; i++)
        cout << vertexPairs[i] << "\n";
    
    return 0;
}