엘리스 코드 챌린지 Day 4

code-challenge.elice.io

 

엘리스 코드 챌린지 Day 4에는 '트리 위의 게임'이라는 문제가 나왔습니다.

Day 3처럼, 알고리즘 문제를 평소에 풀어보지 않은 사람들에게는 다소 어려울 수 있는 난이도로 나왔습니다.

 

저는 오늘부터 알람을 10시에 맞춰두고 풀기로 했습니다.

9등!

 

$\mathrm{dfs}(s,\cdot)$이 $s$에서 게임을 시작했을 때 얻을 수 있는 점수라고 정의합시다.

 

게임에서 가능한 수들이 공개되어 있고, 사람에 따라 가능한 게임 속 시행에 차별이 없다면 보통, 게임은 사이클이 없는 방향 그래프(DAG; directed acyclic graph)로 모델링 되며, 각 게임의 상태는 정점 하나로 표현되고 정점은 승리 또는 패배의 상태를 갖게 됩니다.

 

어떤 상태에서 진행할 수 있는 모든 상태가 승리라면 이 상태는 패배입니다. 다음 턴에 상대방이 승리하지 않게 만들 수 없기 때문입니다.

반대로, 어떤 상태에서 진행할 수 있는 패배 상태가 있다면 이 상태는 승리입니다. 다음 턴에 상대방을 패배하게 만들 수 있기 때문입니다.

 

이러한 이해를 바탕으로 dfs에서 점수를 부호를 바꿔가며 가져올 수 있고, 승리 상태와 패배 상태를 구분할 수 있게 됩니다.

 

참고로 아래 코드는 반례가 존재하지만, 사이트의 데이터가 약해서인지 100점을 받고 있습니다. 어디가 틀렸을까요?

mx의 값이 -1e9보다 더 작아야 합니다.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+3;
int n;
vector<int> adj[N];
bool wins[N];

int64_t dfs(int s = 1, int e = 0) {
    if (size(adj[s]) == 1) {
        wins[s] = true;
        return s;
    }
    int64_t mx = -1e9;
    for (auto u : adj[s]) if (u != e) {
        mx = max(mx, s-dfs(u,s));
    }
    wins[s] = mx>=0;
    return mx;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i=1; i<n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs();
    for (int i=1; i<=n; ++i) {
        cout << wins[i] << '\n';
    }
}