엘리스 코드 챌린지 Day 4 트리 위의 게임

문제

 

풀이

처음 이 문제를 봤을 때 지문에 대한 이해를 전혀 못했습니다.

말을 1인 1개씩 2개를 놓고 게임을 하는건지, 말 1개를 놓고 둘이서 게임을 하는건지도 이해가 안돼서 로직을 그리는 내내 예시도 맞지 않아서 답답했었습니다.

 

문제를 이해하는데 4시간은 걸린것 같습니다.

이 문제는 말을 1개만 놓고 둘이서 게임하는게 맞고, 1번 정점이 루트인 트리라고 명시가 되어있기 때문에 1번 정점부터 방향그래프처럼 순회하도록 합니다.

 

한 번씩 번갈아가면서 점수를 가져가기 때문에 선공의 입장에서는 +, 후공의 입장에서는 -으로 계산할 수 있습니다.

서로 최대한 이기려고 할 것이고, 이기는 경우가 하나라도 존재한다면 이기는 것이기 때문에 가능한 높은 점수를 얻는 것이 중요합니다.

그럴려면 자식 노드의 점수들 중 최솟값을 본인 점수에서 빼는 것으로 계산할 수 있습니다.

선공의 입장에서 계산했기 때문에 해당 노드의 점수가 0 이상이면 선공의 승리, 음수면 후공의 승리가 될 것입니다.

 

2번째 예시로 로직을 설명드리면 루트는 1번, 리프는 4, 5, 6번 노드입니다.

4, 5, 6번 노드에 도착하면 해당 번호만큼 점수를 추가합니다. 그러면 4, 5, 6번 노드의 점수는 4, 5, 6입니다.

 

2번 노드에서는 자신의 번호인 2에서 유일한 자식인 4번 노드의 점수 4를 뺀 값을 저장합니다. 그러면 2번 노드의 점수는 -2가 됩니다.

 

3번 노드는 자식이 2개 있습니다.

5번, 6번 노드의 점수 중 최솟값을 3에서 빼줍니다. 그러면 3번 노드의 점수는 3 - 5 = -2 입니다.

 

마지막 1번 노드입니다.

1번 노드의 자식인 2, 3번 노드 모두 점수가 -2이므로 1 + 2 = 3 점을 얻습니다.

 

그러면 최종 점수 배열은 [3, -2, -2, 4, 5, 6] 이 되고, 0 이상의 점수에는 1, 음수 점수에는 0을 출력하도록 합니다.

 

 

코드

#include <iostream>
#include <vector>
#include <cstring>
#define MAX 100001
using namespace std;
 
vector<int> graph[MAX];
bool visit[MAX];
int score[MAX];
int N;
 
int dfs(int v) {
    visit[v] = true;
 
    int tmp = 1e9;
    for (auto next : graph[v]) {
        if (visit[next]) continue;
        tmp = min(tmp, dfs(next));
    }
    if (tmp == 1e9) tmp = 0;
 
    return score[v] = -tmp + v;
}
 
void func() {
    dfs(1);
 
    for (int i = 1; i <= N; i++) {
        if (score[i] >= 0) cout << "1\n";
        else cout << "0\n";
    }
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 1; i < N; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}