[ day 4 ] 트리 위의 게임

트리 위의 게임

• 시간 제한: 1 초

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

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

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

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

 

---

 

외부에서 작성한 코드를 복사 및 붙여넣기 시, 정확한 코드 작성 시간 산정이 힘들어 수상 과정에서 불이익이 발생할 수 있습니다. 이는 운영진 측에서 확인이 가능한 사항이므로, 모든 코드는 엘리스 플랫폼 내에서 작성을 부탁드립니다.

또한, ChatGPT나 생성 AI, 외부 API 사용 시 수상에서 불이익을 받을 수 있다는 점도 같이 참고 부탁드립니다.

 

입력

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

---

출력

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

---

입력 예시 1

5
1 3
2 1
3 4
5 1

출력 예시 1

1
1
0
1
1

---

입력 예시 2

6
1 3
1 2
3 5
3 6
2 4

출력 예시 2

1
0
0
1
1
1

 

 

작성 코드 

# 많이 어렵다 이거 해설 꼭 봐야할듯.;;;

# 그림으로 보니 숫자가 홀수면 이김. 원리를 모르겠어서 공부 필수.

N = int(input())

# graph = [ set() for _ in range(N+1) ]

# for _ in range(N-1):
#     u, v = map(int,input().split())
#     graph[u].add(v)
#     graph[v].add(u)
# 방향성 없는 그래프인줄알았는데 자식노드 이야기하는거보면 아닌듯

graph = [ [] for _ in range(N+1) ]


for _ in range(N-1):
    u, v = map(int,input().split())
    if u < v :
        graph[u].append(v)
    else :
        graph[v].append(u)
    # graph[v].append(u)

# 정답은 최소 깊이가 홀수이거나
# 최대 깊이가 홀수인 경우 일것이다.

maxdepth = -1

def DFS(start, graph, total):
    global maxdepth

    if graph[start]:
        for i in graph[start]:
            DFS(i,graph,total+1)
    else :
        maxdepth = max(maxdepth,total)

for i in range(1,N+1):
    maxdepth = -1
    DFS(i,graph,1)
    if maxdepth%2 != 0:
        print("1")
    else:
        print("0")

 

솔직하게 말하면 문제가 좀 이해가 되지않는다. 조건이 방향성 그래프인지, 후공은 어디서 시작하는지 ;; 3번에서 시작할때 도데체 어떻게 후공이 이기는건지 주어진 예시를 그려서 한번 사고해봤는데도 문제가 무슨 알고리즘으로 동작하는지 이해하기가 어렵다;;

 

이게 선공의 말 있는곳의 노드가 없으면 바로 끝나는건지 서로 말이 중복되서는 안되는것인지;; 그냥 문제가 내가 멍청해서인지 이해하기 어렵다.

 

 

문제의 재해석 :

1. 최장 길이 노드 방향 찾기
2. 길이가 같다면, 시작 지점 다음 노드 간의 크기가 큰 쪽을 후공이 선택
3. 그러면 그 방향대로 선공 - 후공 - 선공 식으로 번갈아가면서 리프까지 쭉 하강
4. 그 동안의 노드 값 다 합치고 크기 비교해서 출력 1 or 0

 

N = int(input())

Edge = [ [] for _ in range(N+1)]

MaxDepth = [ -1 for _ in range(N+1)]

for _ in range(N-1):
    u, v = map(int, input().split())
    # Edge[u].append(v)
    if u < v :
        Edge[u].append(v)
    else:
        Edge[v].append(u)

maxdepth = -1

def DFS(start, Edge, total):
    global maxdepth

    if Edge[start]:
        for i in Edge[start]:
            DFS(i,Edge,total+1)
    else:
        maxdepth = max(maxdepth,total)


for i in range(1,N+1):
    maxdepth = -1
    DFS(i,Edge,1)
    MaxDepth[i] = max(MaxDepth[i],maxdepth)

# print(MaxDepth) # 이제 각 노드의 가장 깊은 숫자를 갖게됨

# 플로이드 워셜 알고리즘 쓸수 있겠다. > 하지만 안쓸것임 나중에재구현 해볼듯

for i in range(1,N+1):
    H = i  # Horse
    F = 0  # First
    S = 0  # Second
    D = MaxDepth[i] # Depth
    for j in range(MaxDepth[i]+1):
        F += H
        if Edge[H]: # 연결된거 확인
            bestNext = []
            for k in Edge[H]: # 연결된거 확인하면서
                if MaxDepth[k] == D-1:
                    bestNext.append(k)
            bestNext.sort()
            H = bestNext[-1]
            D -= 1
        else:
            if F >= S:
                print(1)
            else:
                print(0)
            break
        S += H
        if Edge[H]: # 연결된거 확인
            bestNext = []
            for k in Edge[H]: # 연결된거 확인하면서
                if MaxDepth[k] == D-1:
                    bestNext.append(k)
            bestNext.sort()
            H = bestNext[-1]
            D -= 1
        else:
            if F >= S:
                print(1)
            else:
                print(0)
            break

 

=>  예시 출력만 맞음

 

길이의 접근이 아닌 점수의 접근 시도.

1. 최대 점수 노드 방향 찾기
2. 점수가 같다면, 시작 지점 다음 노드 간의 크기가 큰 쪽을 후공이 선택
3. 그러면 그 방향대로 선공 - 후공 - 선공 식으로 번갈아가면서 리프까지 쭉 하강
4. 그 동안의 노드 값 다 합치고 크기 비교해서 출력 1 or 0

 

N = int(input())

Edge = [ [] for _ in range(N+1)]

MaxDepth = [ -1 for _ in range(N+1)]

for _ in range(N-1):
    u, v = map(int, input().split())
    # Edge[u].append(v)
    if u < v :
        Edge[u].append(v)
    else:
        Edge[v].append(u)

maxdepth = -1

def DFS(start, Edge, total):
    global maxdepth

    if Edge[start]:
        for i in Edge[start]:
            DFS(i,Edge,total+i)
    else:
        maxdepth = max(maxdepth,total)


for i in range(1,N+1):
    maxdepth = -1
    DFS(i,Edge,i)
    MaxDepth[i] = max(MaxDepth[i],maxdepth)

print(MaxDepth) # 이제 각 노드의 가장 깊은 숫자를 갖게됨

# 플로이드 워셜 알고리즘 쓸수 있겠다. > 하지만 안쓸것임 나중에재구현 해볼듯

for i in range(1,N+1):
    H = i  # Horse
    F = 0  # First
    S = 0  # Second
    D = MaxDepth[i] # Depth
    while True:
        F += H
        if Edge[H]: # 연결된거 확인
            bestNext = -1
            cur = -1
            for k in Edge[H]: # 연결된거 확인하면서
                if MaxDepth[k] > bestNext:
                    bestNext = MaxDepth[k]
                    cur = k
            H = k
        else:
            if F >= S:
                print(1)
            else:
                print(0)
            break
        S += H
        if Edge[H]: # 연결된거 확인
            bestNext = -1
            cur = -1
            for k in Edge[H]: # 연결된거 확인하면서
                if MaxDepth[k] > bestNext:
                    bestNext = MaxDepth[k]
                    cur = k
            H = k
        else:
            if F >= S:
                print(1)
            else:
                print(0)
            break

 

;; 역시 예시 출력만 맞음

 

그냥 모든 노드 경우의 수 만큼 전부 선공 후공 서로 점수 비교해보기

 

N = int(input())

Edge = [ [] for _ in range(N+1)]

MaxDepth = [ -1 for _ in range(N+1)]

for _ in range(N-1):
    u, v = map(int, input().split())
    Edge[u].append(v)
    # if u < v :
    #     Edge[u].append(v)
    # else:
    #     Edge[v].append(u)



isFwin = True

def DFS(start, Edge, F, S , curturn):
    global isFwin

    if curturn == "F":
        F += start
    else:
        S += start

    if Edge[start]:
        for i in Edge[start]:
            if curturn == "F": # F턴
                DFS(i,Edge,F,S,"S")
            else :
                DFS(i,Edge,F,S,"F")
    else:
        if S > F:
            isFwin = False
        


for i in range(1,N+1):
    F = 0
    S = 0
    isFwin = True
    DFS(i,Edge,F, S,"F")
    if isFwin:
        print(1)
    else:
        print(0)

 

이것도 예시 문제만 맞고 틀렸다.

문제를 어떻게 풀어야할지 너무 이해가 안된다. ㅠㅠ 조건에대해 너무 명확하지 않다고 느껴져서 구현하기가 힘들다.

아직 내 실력으론 본선에 나가는 것은 어려울 것 같다는 생각이 들었다.

 

 

 

 

다른 인원이 작성한 코드 알고리즘 따라 파이썬 구현 :

from collections import deque, defaultdict

def bfs(start):
    Que = deque([start])
    visited[start] = True

    while Que:
        node = Que.popleft()
        temp.append(node)
        for neighbor in Edge[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                Que.append(neighbor)

def check():
    while temp:
        node = temp.pop()
        visited[node] = True
        is_leaf_node = True
        min_value = float('inf')
        for child in Edge[node]:
            if visited[child]:
                is_leaf_node = False
                min_value = min(min_value, Score[child])
        Score[node] = node if is_leaf_node else (node-min_value)

N = int(input())
Edge = defaultdict(list) # 그래프 인접 간선 저장
Score = [0] * (N+1) # 각 노드 점수
visited = [False] * (N+1)
temp = []

for  _ in range(N -1):
    u,v = map(int, input().split())
    Edge[u].append(v)
    Edge[v].append(u)

bfs(1)
visited = [False] * (N+1)
check()

for i in range(1,N+1):
    print(1 if Score[i]>=0 else 0)

 

=> 문제 조건 모두 통과한 코드.

 

어떻게 동작하는지 한번 파악해보겠다.

 

문제에서 주어진 대로 입출력을 받고,

 

초기 설정 및 입력 처리

N = int(input()) # 문제에서 주어진 N = 트리 노드수임
Edge = defaultdict(list) # 엣지
Score = [0] * (N + 1) # 각 노드별 점수 저장 리스트
visited = [False] * (N + 1) #방문여부 판단
temp = [] # BFS과정에서 방문한 노드 저장 임시 리스트

for _ in range(N - 1):
    u, v = map(int, input().split())
    Edge[u].append(v)
    Edge[v].append(u)

 

BFS 함수

BFS 함수는 (너비 우선 탐색)를 통해 시작 노드로부터 연결된 모든 노드를 탐색하고, 각 노드를 temp 리스트에 저장합니다.

def bfs(start):
    Que = deque([start])
    visited[start] = True

    while Que:
        node = Que.popleft()
        temp.append(node)
        for neighbor in Edge[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                Que.append(neighbor)

 

Check 함수

check 함수는 temp 리스트에 저장된 노드들을 사용하여 각 노드의 점수를 계산합니다. 각 노드의 점수는 다음과 같은 규칙을 따릅니다:

• 리프 노드의 점수는 노드 번호 그 자체입니다.
• 비리프 노드의 점수는 그 노드 번호에서 자식 노드의 최소 점수를 뺀 값입니다.

def check():
    while temp:
        node = temp.pop()
        visited[node] = True
        is_leaf_node = True
        min_value = float('inf')
        for child in Edge[node]:
            if visited[child]:
                is_leaf_node = False
                min_value = min(min_value, Score[child])
        Score[node] = node if is_leaf_node else (node - min_value)

 

위 함수를 실행하고 for 문을 돌면서 각 노드의 점수가 0 이상이면 선공이 이기므로 1을 출력하고, 그렇지 않으면 0을 출력합니다.

bfs(1)
visited = [False] * (N + 1)
check()

for i in range(1, N + 1):
    print(1 if Score[i] >= 0 else 0)

 

요약

• BFS를 사용하여 트리의 모든 노드를 탐색하고, temp 리스트에 저장합니다.
• check 함수는 temp 리스트의 노드를 사용하여 각 노드의 점수를 계산합니다.
• 각 노드의 점수를 기준으로 선공이 이기는지 후공이 이기는지를 출력합니다.

해결

1. 트리 탐색 (BFS): BFS를 통해 트리를 탐색하면서 각 노드를 기록합니다.
2. 점수 계산: 각 노드의 점수를 계산합니다. 리프 노드는 자신의 번호가 점수가 되고, 다른 노드는 자신의 번호에서 자식 노드의 최소 점수를 뺀 값이 점수가 됩니다.
3. 결과 출력: 각 노드의 점수가 0 이상이면 선공이 이긴 것이므로 1을 출력하고, 그렇지 않으면 후공이 이긴 것이므로 0을 출력합니다.

 

정답 코드 

C++

#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';
	}
}

Python

from collections import defaultdict

v=defaultdict(list)
dp=[None]*100050
inf=int(1e12)

def dfs(x:int ,par:int):
    global dp,v
    
    ret=inf
    
    for nxt in v[x]:
        if nxt==par:
            continue
            
        dfs(nxt,x)
        ret=min(ret,dp[nxt])
        
    if ret==inf:
        ret=0
        
    dp[x]=x-ret

n=int(input())

for _ in range(1,n):
    a,b=(map(int,input().split()))
    v[a].append(b)
    v[b].append(a)

dfs(1, 0)

for i in range(1,n+1):
    print('1' if dp[i]>=0 else '0')

Java

import java.util.*;

class Main {
    static long n, a, b;
    static ArrayList<Long>[] v = new ArrayList[100050];
    static long[] dp = new long[100050];
    static final long inf = (long)1e12;

    static void dfs(long x, long par) {
        long ret = inf;
        for (Long nxt : v[(int)x]) {
            if (nxt == par) continue;
            dfs(nxt, x);
            ret = Math.min(ret, dp[nxt.intValue()]);
        }
        if (ret == inf) ret = 0;
        dp[(int)x] = x - ret;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);  
        
        n=scanner.nextLong();
        
        for(int i=0;i<100050;i++)
            v[i]=new ArrayList<>();
            
        for(int i=1;i<n;i++){
            a=scanner.nextLong();
            b=scanner.nextLong();
            
            v[(int)a].add(b);
            v[(int)b].add(a);
        }
        
       dfs(1,0);
       
       for(int i=1;i<=n;i++){
           if(dp[i]>=0)
               System.out.println("1");
           else
               System.out.println("0");
       }
   } 
}