[bfs] 백준 15900 나무 탈출

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

처음에 풀었을 때는 시간 초과가 떴습니다.

#include <iostream>
#include <vector>
using namespace std;
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tr[500001]= {0}; tr[1] = 1;
    bool leaf[500001] = {0}; //if leaf -> false
    vector<int> v;
    int N,a,b;
    long long dis = 0;
    
    cin >> N;
 
    for(int i = 1; i <= N-1; i++){
        cin >> a >> b;
        if(!tr[b]) {tr[b] = a;leaf[a] = true;}
        if(!tr[a]) {tr[a] = b;leaf[b] = true;}
    }
    
    for(int i = 1; i <= N; i++){
        if(!leaf[i]) v.push_back(i);
    }
    
    while(!v.empty()){
        int marker = v.back(); v.pop_back();
        while(marker != 1){
            dis+=1;
            marker = tr[marker];
        }
    }
    
    if(dis%2) cout << "Yes";
    else cout << "No";
}

트리 구현이랑, 트리 탐색(?)에서 좀 막혀서 dfs로 푼 다른 소스보고 참고해서 풀었습니다.

저는 bfs 구현이 더 재미있고 좀 쉽더군요. 재귀함수는 영....

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> tr[500001];
bool visited[500001];
int layer[500001];
long long ret;
 
void bps(int start, long long dist);
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N,a,b;
    
    cin >> N;
    
    for(int i = 1; i <= N-1; i++){
        cin >> a >> b;
        tr[b].push_back(a);
        tr[a].push_back(b);
    }
    
    bps(1,0);
    if(ret%2) cout << "Yes";
    else       cout << "No";
}
 
void bps(int start, long long dist){
    queue<int> q;
    q.push(1); visited[1] = true;
    int layer_chk = 1;
    layer[1] = 1;
    
    while(!q.empty()){
        int tmp = q.front(); q.pop();
        
        if(layer_chk != layer[tmp]){
            dist+=1;
            layer_chk = layer[tmp];
        }
        
        if(tr[tmp].size() == 1 && visited[tr[tmp].back()]){
            ret+=dist;
            continue;
        }
        
        while(!tr[tmp].empty()){
            int v_tmp = tr[tmp].back(); tr[tmp].pop_back();
            
            if(visited[v_tmp]) continue;
            
            q.push(v_tmp);
            visited[v_tmp] = true;
            layer[v_tmp] = layer[tmp] +1;
        }
 
    }
}