엘리스 - 트리 위의 게임(C++)

코딩 첼린지? 문제여서 제공이 되는 지 모르겠다. 문제는 다음과 같다.

 

트리 위의 게임

• 시간 제한: 1 초

정점 N개의 트리에서 두 사람이 게임을 진행하려 한다.
각 정점은 1번부터 N번 까지 번호가 매겨져 있고 루트노드는 1번 노드이다.
게임은 서로 턴을 번갈아 가며 진행되고 트리 위에 놓을 수 있는 말과 함께 진행된다.
두 사람의 점수는 모두 0점으로 시작한다.

각 턴마다 두 사람은 다음과 같은 작업을 반복한다.

• 현재 말이 놓여 있는 정점의 번호만큼 자신의 점수에 더한다.
• 현재 말이 놓여 있는 정점의 자식 정점이 없다면 그대로 게임을 종료한다.
  자식 정점이 존재한다면 자식 정점 중 원하는 자식 정점으로 말을 옮긴다.

게임이 종료되었을 때 선공의 점수가 후공의 점수보다 높거나 같다면 선공이 승리하고 아니라면 후공이 승리한다.
두 사람이 최적으로 플레이할 때, 처음 말이 놓여져 있는 정점의 번호에 따라 선공이 이기는지 후공이 이기는지 구해보자.

 

 

입력

• 첫째 줄에 정점의 수 N이 주어진다.
  
  1≤N≤100000
• 둘째 줄부터 N−1개의 줄에 간선을 나타내는 정수 u,v가 주어진다.
  
  1≤u,v≤N
• • 이는 u번 정점과 v번 정점을 잇는 간선이 존재한다는 뜻이다.

---

출력

• N개의 줄에 걸쳐 정답을 출력한다.
• i번째 줄에는 말의 시작위치가 i번 정점일 때의 결과를 출력한다.
• 선공이 이긴다면 1을 후공이 이긴다면 0을 출력한다.

 

DFS 를 사용해야 하는 것은 자명하고 DFS 백트래킹을 사용하면 된다고 생각했다. 각 플레이어에게 "최선" 이란 선공의 경우 자신의 점수는 최대로, 후공의 점수는 최저로 설정하는 것이 본인에게 "최선" 의 선택이 된다. 그래서 이 하나의 기준을 가지고 움직이면 된다.

 

아무리 선공이 최선으로 움직여도 패배하는 경우는 당연히 나온다. 이 경우는 후공이 "최선"의 행동을 했다고 볼 수 있다.

그래서 DFS 백트래킹으로 모든 곳을 돌며 선공 플레이어가 완벽하게 플레이했을 경우 즉, 본인의 점수는 갱신했고 후공의 점수는 더 낮게 갱신할 경우에 점수를 갱신하도록 만들었다.

 

그런데 틀렸다.... 무언가 반례가 있을탠데 아쉽게 찾지 못했다. 차라리 시간초과가 났다면 납득했을 것이다.

 

답지를 보니 DP를 통해 한번의 백트래킹으로 문제를 해결했다. 매우 좋은 문제라고 생각해서 종종 다시 풀어볼 생각이다.

 

DP[N] = N에서 선공이 시작했을 경우, 선공의 최선값 - 후공의 최선값 

 

이것을 염두해두고 문제를 풀수 있다. 위의 의미가 무엇일까? 왜 뺀 값을 가져올까? 그 의미는 더 진행하다보면 알 수 있다.

 

만약 1의 다음 노드들이 2, 3, 4 가 있다고 하자. 

 

그렇다면 DP[2] = 2 , DP[3] = 3, DP[4] = 4 가 될 것이다. 1의 경우 다음 노드들 중 "최소 DP[next] 값" 을 저장해둬야한다. 왜냐하면

 

현재 DP[NEXT] 는 NEXT 노드에서 시작할 때 "선공" 이다. 하지만 ? N에서 시작한다면 NEXT는 "후공" 이다. 다시 말해 선공 - 후공의 최소값을 가져온다는 것은, 최대의 후공을 가져오는 것과 같다! 이제 후공은 선공의 점수 + N이기 때문이다.

 

그래서 DP[N] = N + 후공 - 선공이 된다.

 

코드로 구현하는 것이 어려운데 다음 노드들의 DP값 중 최소값을 가져와 DP 값을 갱신한다.

 

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

bool visited[100001];
vector<int> node[100001];
ll dp[100001];

void dfs(int N){
    visited[N] = true;
    ll res = 1e12;
    for(int next : node[N]){
        if(visited[next]) continue;
        visited[next] = true;
        dfs(next);
        visited[next] = false;

        res = min(dp[next], res);
    }

    if(res == 1e12) res = 0;
    dp[N] = N - res;
}

int main() {
    int n; cin >> n;

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

    dfs(1);

    for(int i = 1; i<= n; i++){
        if(dp[i] >= 0) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}