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

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

11725번: 트리의 부모 찾기

 

문제 요약

 

루트 없는 트리.

트리의 루트가 1일 때, 각 노드의 부모를 구하라

 

범위

 

노드의 개수 N (2 ≤ N ≤ 100,000)

 

 

 

---

 

모든 정점을 탐색해서 모든 노드의 부모 노드를 찾으면 되므로 이는 DFS 혹은 BFS 중 하나를 선택해서 코드를 구현하면 된다.

 

 

BFS

BFS는 한 노드에서부터 시작해서 방문한 노드를 큐에 넣으면서 진행한다. 큐에 들어간 노드의 인접 노드를 반복문을 통해 방문하게 되는데, 이때 x는 현재 방문 노드, y는 인접 노드를 의미하므로 parent 배열에 노드 y의 부모 노드인 x를 저장한다.

2번 노드부터 순서대로 부모 노드의 값을 출력해야 하므로 탐색 내에서 parent 배열에 값을 저장하도록 하고 모든 탐색이 끝나면 차례대로 2번 노드부터 출력하도록 했다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, n1, n2, parent[100002];
vector<int> v[100002];
bool visited[100002];

void input(){
    cin >> n;
    for(int i=0; i<n-1; i++){
        cin >> n1 >> n2;
        v[n1].push_back(n2);
        v[n2].push_back(n1);
    }
}

void bfs(int s){
    queue<int> q;
    visited[s] = true;
    q.push(s);
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(int i=0; i<v[x].size(); i++){
            int y = v[x][i];
            if(visited[y]) continue; //방문한적이 있으면 패스
            parent[y] = x;           //부모 노드 번호 저장
            visited[y] = true;
            q.push(y);
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    bfs(1);
    for(int i=2; i<=n; i++) cout << parent[i] << '\n';
    return 0;
}

 

 

 

 

DFS의 경우, 좀 더 간단한 코드를 작성할 수 있다.

트리의 루트가 1이라고 고정되어있기 때문에 1부터 시작해서 재귀 호출을 통해 다음 인접 노드로 이동한다.

방문한 노드는 넘어가고 부모노드값(x)은 저장한다. 그 이후로는 BFS와 동일하게 진행한다.

 

 

#include <iostream>
#include <vector>
using namespace std;
int n, n1, n2, parent[100002];
vector<int> v[100002];
bool visited[100002];

void input(){
    cin >> n;
    for(int i=0; i<n-1; i++){
        cin >> n1 >> n2;
        v[n1].push_back(n2);
        v[n2].push_back(n1);
    }
}

void dfs(int x){
    visited[x] = true;
    for(int i=0; i<v[x].size(); i++){
        int y = v[x][i]; //인접노드
        if(visited[y]) continue; //방문노드는 패스
        parent[y] = x; //부모노드값 저장
        dfs(y);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    dfs(1);
    for(int i=2; i<=n; i++) cout << parent[i] << '\n';
    return 0;
}

 

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!