[백준/C++] 11725 번 : 트리의 부모 찾기

11725번 : 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

---

문제

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

 

입력

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

 

출력

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

---

그래프를 차분히 풀어보면 알 수 있는 문제이다.

참고하면 좋은 비슷한 그래프 문제 : silver-g-0114.tistory.com/20

[백준/C++] 11724번 : 연결 요소의 개수 풀이

 

처음엔 각 노드의 부모를 정확히 알 수 없으므로 무방향 그래프로 접근한 다음 방문 표시를 통해 부모 노드를 구분했다.

트리의 루트가 1이므로 1부터 DFS 탐색을 시작한다.

 

#include <iostream>
#include <vector>
#define MAX 100000

using namespace std;

int n;
vector<int> graph[MAX];
int ans[MAX]; // 트리의 부모 저장
bool visited[MAX];

void dfs(int node){
    visited[node] = true;
    
    for(int i=0; i<graph[node].size(); i++){
        int next = graph[node][i];
        if(!visited[next]){
            ans[next] = node;
            dfs(next);
        }
    }
}

int main(void){
    
    cin >> n;
    for(int i=1; i<n; i++){
        int node1, node2;
        cin >> node1 >> node2;
        
        // 무방향 그래프
        graph[node1].push_back(node2);
        graph[node2].push_back(node1);
    }
    
    dfs(1);
    for(int i=2; i<=n; i++){
        cout << ans[i] << endl;
    }
    
    return 0;
}

시간 초과 에러 ㅠㅠ

간단한 탐색 문제네!! 하고 풀었더니 .. 시간 초과 에러가 났다.

딱히 에러도 없고 푸는 방법도 탐색이 맞는 것 같아 출력 방법에서의 문제일 것 같았다. 

출력 속도 참고 자료 : www.acmicpc.net/blog/view/57

출력 속도 비교

ios_base::sync_with_stdio(false);
cout.tie(NULL);

그리고 MAX 범위도 수정했다. (런타임 에러)

#define MAX 100001 // 100000 -> 100001

 

최종 풀이

#include <iostream>
#include <vector>
#define MAX 100001

using namespace std;

int n;
vector<int> graph[MAX];
int ans[MAX]; // 트리의 부모 저장
bool visited[MAX];

void dfs(int node){
    visited[node] = true;
    
    for(int i=0; i<graph[node].size(); i++){
        int next = graph[node][i];
        if(!visited[next]){
            ans[next] = node;
            dfs(next);
        }
    }
}

int main(void){
    
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    
    cin >> n;
    for(int i=1; i<n; i++){
        int node1, node2;
        cin >> node1 >> node2;
        
        // 무방향 그래프
        graph[node1].push_back(node2);
        graph[node2].push_back(node1);
    }
    
    dfs(1);
    for(int i=2; i<=n; i++){
        cout << ans[i] << '\n';
    }
    
    return 0;
}

풀이 인증

입출력 시간 문제, 인덱스 범위에 유의하자!