[백준] 15900번 나무탈출 (C++)

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

 

 

이 문제는 하나의 루트가 1인 트리가 주어졌을때 리프노드에 말이 놓여져 있고 2명이 게임을 하는데

승자가 성원이인지 아닌지에 대한 여부를 출력하는 문제이다.

 

문제 조건을 보면 리프노드에 말이 놓여져 있으며 말을 움직일때 무조건 현재 놓여져 있는 노드의 부모 노드로만 움직일 수 있으며
루트(1 노드)에 도착할 경우 말은 제거가 된다.

 

이때 현재 턴에 말을 선택할 수 없는 사람이 게임을 지게된다.

 

 

이 문제를 풀기 위해선 입력으로 주어지는 간선을 연결리스트로 만든 후 1에서부터 연결된 노드를 계속 호출하며 노드에 대한

depth를 기록해야 한다. 

 

즉 나의 방법은

1. 1에서 부터 dfs를 호출하여 노드에 대한 깊이를 dp배열로 기록한다.

2. dfs함수 내에서 다음 자식으로 갈 수 없게 된다면 이는 리프노드이기 때문에 리스트에 노드를 넣어준다.

3. 마지막으로 리스트를 순회하며 리프노드에서 1까지 거리를 더해준다.

4. 성원이가 게임을 먼저 시작하기 때문에 성원이는 홀수에 턴을 시작한다. 즉 거리가 홀수인 경우는 성원이가 이기고

짝수인 경우는 성원이가 게임에 지게 된다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N;
vector<vector<int>> v(500001);
bool visited[500001];
vector<int> tmp;
int dp[500001];

void dfscnt(int Node, int depth) {		// 1에서부터 노드들의 깊이를 기록하기 위한 함수
    visited[Node] = true;
    dp[Node] = depth;

    for(auto it : v[Node]) {
        if(!visited[it]) {
            dfscnt(it, depth+1);
        }
    }
}

void dfs(int Node) {					// 리프노드를 알기위한 함수
    visited[Node] = true;
    bool flag = true;

    for(auto it : v[Node]) {
        if(!visited[it]) {
            dfs(it);
            flag = false;
        }
    }

    if(flag) {
        tmp.push_back(Node);
    }
}

void solve() {
    dfs(1);

    memset(visited, 0, sizeof(visited));

    dfscnt(1, 0);

    int result = 0;

    for(auto it : tmp) {
        result += dp[it];
    }

    if(result % 2 == 0) {
        cout << "No";
    }
    else {
        cout << "Yes";
    }
}

void input() {
    cin >> N;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

지금 보면 dfs 함수를 2번 호출하고 있는데 한번으로 끝날 수 있는데 저때는 생각이 안나서 저런것 같다

문제를 풀때 조금 최적화적으로 더 생각해야 할 것 같다.