백준 - 32645 동까뚱뽭 게임

 

해결과정 - 트리 탐색

1. 리프노드에서는 반드시 혁준이가 이긴다

2. 어떤 노드에서 시작하였을때 누가 반드시 이기는지를 리프노드에서부터 탐색한다

3. 동우가 시작하는 노드의 자식노드들중 혁준이가 이기는 노드가 있으면 그 시작노드는 반드시 동우가 이긴다

 

이 3가지를 이용하니 문제가 수월하게 해결되었다

 

처음에는 트리의 자식노드의 개수를 묻는 문제인줄알았지만 곰곰히 생각해보니 다른 문제였다.

 

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<bool> depth; 

bool dfs(int cur, int parent){
    bool check = false;
    for(int i = 0 ; i < adj[cur].size(); i++){
        int next = adj[cur][i];
        if(next == parent) continue;
        if(dfs(next, cur) == false){
            check = true;
        }
    }
    depth[cur] = check;
    return check;
}

int main() {
    int n; cin >> n;
    adj.resize(n + 1);
    depth.resize(n + 1);
    
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    // 자식의 개수 찾기
    int start = 1;
    dfs(start, start);

    for(int i = 1; i < n + 1; i++){
        if(depth[i]) cout << "donggggas\n";
        else cout << "uppercut\n";
    }
    
    return 0;
}

 

후기

노트북 고장난지 5일째 수리가 언제될지 몰라서 그냥 컴퓨터를 샀다 ㅎㅎ

7900에 4060정도면 드디어 언리얼로 출격할 수 있을거 같다네 ㅎㅎ