[백준(BOJ)] 11725번 : 트리의 부모 찾기 - C++[CPP]

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

11725번: 트리의 부모 찾기

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

단순 트리의 부모만 구하면 되는 문제다. DFS, BFS 두 가지 풀이 방법이 있는데 DFS로 풀어봤다.

vector에 값을 대칭으로 입력한다. 그리고 자식노드에 하나씩 방문하여 부모를 지정해주는 로직으로 풀었다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>

using namespace std;
#define MAX 100001

int N;
int arr[MAX];
bool visited[MAX];
vector<int> v[MAX];

void dfs(int k) {
    visited[k]=true;
    for(int i=0;i<v[k].size();i++) {
        int next = v[k][i];
        if(!visited[next]) {
            arr[next]=k;
            dfs(next);
        }
    }
}

int main() {
    cin >> N;

    for(int i=0;i<N;i++) {
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1);

    for(int i=2;i<=N;i++) cout << arr[i] << "\n";
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!