[백준/Baekjoon] 11725 트리의 부모 찾기 C++ :: Recursion & Graph

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

11725번: 트리의 부모 찾기

---

1. Logic

재귀를 이해하고 있다면 쉽게 풀 수 있는 문제이다.

각 노드의 부모 노드를 순서대로 출력해야 하기 때문에 부모 노드를 저장하는 배열(check)에 저장해줬다. 

 

양방향으로 입력을 받았기 때문에 반복되는 계산을 막아주기 위해 vis배열도 추가해줬다.

수정 > 원래는 vis배열에 넣어줬지만 check배열을 -1로 초기화 시켜준 다음 -1이 아니면 continue하도록 설계해주면 100001개짜리 배열 하나를 덜 써도 된다

---

2. Code

#include <iostream>
#include <vector>

using namespace std;

int n;

vector<int> tree[100001];
bool vis[100001];
int check[100001];

void solve(int cur, int prev) {
    check[cur] = prev;
    for(int i = 0; i < tree[cur].size(); i++) {
        if(vis[tree[cur][i]]) continue;
        vis[cur] = true;
        solve(tree[cur][i], cur);
        vis[cur] = false;
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    
    solve(1, 0);
    vis[1] = true;
    
    for(int i = 2; i <= n; i++) {
        cout << check[i] << "\n";
    }
}

수정 코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n;

vector<int> tree[100001];
int check[100001];

void solve(int cur, int prev) {
    check[cur] = prev;
    for(int i = 0; i < tree[cur].size(); i++) {
        if(check[tree[cur][i]] != -1) continue;

        solve(tree[cur][i], cur);

    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(check, -1, sizeof(check));
    cin >> n;
    
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    
    solve(1, 0);
    
    for(int i = 2; i <= n; i++) {
        cout << check[i] << "\n";
    }
}

---

3. Feedback

알고리즘 처음 시작했던 때가 생각났다. 재귀가 진짜 이해도 안가고 어려워서 헤메고 맨날 물어봤는데 이제는 좀 이해한 것 같아서 행복해~~

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐