엘리스 코드 챌린지 예선 [Day 4] 문제풀이

문제

목표량

• 시간 제한: 1초

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

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

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

지시사항

입력

• 첫째 줄에 정점의 수 N이 주어진다.

1≤ N ≤100000

1 ≤ m ≤ 500

• 둘째 줄부터 N−1개의 줄에 간선을 나타내는 정수 u,v가 주어진다.

1 ≤ u, v ≤ n

• 둘째 줄부터 N−1개의 줄에 간선을 나타내는 정수 u,v가 주어진다.

출력

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

입력 예시

5
1 3
2 1
3 4
5 1

출력 예시

1
1
0
1
1

풀이

접근

- 작성중-

 

풀이

1. 작성
2. 작성

코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

vector<vector<int>> A;
vector<int> Score;
vector<bool> visited;
queue<int> Q;
stack<int> S;

void BFS(int start);
void Check(void);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	A.resize(N + 1);
	Score.resize(N + 1);
	visited.resize(N + 1);

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

	BFS(1);
	visited = vector<bool>(N + 1, false);
	Check();

	for (int i = 1; i <= N; ++i)
		cout << (Score[i] >= 0 ? 1 : 0) << '\n';
	return 0;
}

void BFS(int start)
{
	Q.push(start);
	visited[start] = true;

	while (!Q.empty())
	{
		int node = Q.front();
		Q.pop();
		S.push(node);
		for (int i : A[node])
		{
			if (!visited[i])
			{
				visited[i] = true;
				Q.push(i);
			}
		}
	}
}

void Check(void)
{
	while (!S.empty())
	{
		int node = S.top();
		S.pop();
		visited[node] = true;
		bool IsLeafNode = true;
		int MinValue = INT_MAX;
		for (int child : A[node]) {
			if (visited[child]) {
				IsLeafNode = false;
				MinValue = min(MinValue, Score[child]);
			}
		}

		Score[node] = (IsLeafNode ? node : (node - MinValue));
	}
}

↑ 더보기 클릭으로 펼치기

 

모범답안

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, a, b;
vector<ll>v[100050];
ll dp[100050], inf = 1e12;
void dfs(ll x, ll par) {
	ll ret = inf;
	for (auto nxt : v[x]) {
		if (nxt == par)continue;
		dfs(nxt, x);
		ret = min(ret, dp[nxt]);
	}
	if (ret == inf)ret = 0;
	dp[x] = x - ret;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) {
		if (dp[i] >= 0)cout << "1";
		else cout << "0";
		cout << '\n';
	}
}

↑ 더보기 클릭으로 펼치기

 

후기

체감상 진짜 어려웠다.

주어진 예제 테스트 케이스만 맞다고 나오고, 제출하면 테스트 케이스가 다 틀리다고 나와서 이런 저런 방법으로 구현을

5 ~ 6개는 한 것 같다.