백준 15900 나무 탈출

백준 15900 나무 탈출

---

이번 문제는 나무 탈출이다. 이제 좀 바쁠거 같아서 매일 아침에 한문제라도 제대로 풀기로 했다..!
문제는 dfs 였다. 사실 문제를 이해하는데 한참 걸렸다.

남들한텐 바로 이해될 거였을거 같은데, 핵심은 노드가 하나 떨어져 나가면 밑에 자식 노드들은 다른 간선이 없으면 루트로 도달할 수 가 없기 때문에 이를 고려해야 한다는 것이다.

그렇기에 간단하게 생각하면, 루트 노드에서 자식 노드로 도달하는 방법의 개수를 다 세서 홀수인지, 짝수인지만 나누면 된다ㅎ

#include <iostream>
#include <vector>

using namespace std;

int visited[500002] = {0,};
vector<int> lst[500002];

long sum = 0;

void dfs(int cur, int cnt)
{
    if (lst[cur].size() == 1 && cur != 1)
    {
        sum += cnt;
        return;
    }
    for (int i = 0; i < lst[cur].size(); i++)
    {
        if(visited[lst[cur][i]] ==0 )
        {
            visited[lst[cur][i]] = 1;
            dfs(lst[cur][i], cnt + 1);
            visited[lst[cur][i]] = 0;
        }
    }
}
int main()
{
    int n;
    int a, b;
    cin>>n;

    for (int i = 0; i < n-1; i++)
    {
        cin>>a>>b;
        lst[a].push_back(b);
        lst[b].push_back(a);
    }

    visited[1] = 1;
    dfs(1,0);

    if (sum % 2 == 1)
        cout<<"Yes\n";
    else
        cout<< "No\n";

    return 0;
}

구현 자체는 별거 없는데, 어떻게 풀어야할지에 대해 떠올리는게 쉽지 않았다. 트리라 해서 몇문제 풀어보니 거의 다 dfs, bfs 를 이용하는게 다인거 같으니, 노드니 간선이니 루트니 이런 게 문제에 있으면 dfs 를 이용하는 방식을 우선적으로 고려해 보는게 좋을 것 같다.

오자마자 집에 가고싶다 걍 집에 있고 싶어서 하루 못나오겠다하면 싫어하겠지?