[엘리스][Python] 시즌2. 알고리즘 코드 챌린지 [Day4] - 트리 위의 게임

📚 문제

 

https://code-challenge.elice.io/courses/282926/lectures/2455429/lecturepages/21567985

알고리즘 문제집 | 엘리스 코드 챌린지

 

Day 4

 

---

💡 풀이 과정

• 먼저 간선으로 단방향 트리를 생성해야한다.
• 말단 노드들에서 시작할 경우에는 누가 이길 지 명확하기에 말단에서부터 올라가도록 한다.
  • 말단에서 두 번째 노드 같은 경우에도 선후공 중 누가 이길 지 바로 알 수 있다.
  • 3번 노드에서 선공하는 경우에는 왼쪽으로 가면 (3:2) 승, 오른쪽으로 가면 (3:4) 패이다.
  • 선공은 당연히 오른쪽을 선택할 것이고 이는 왼쪽으로 가면 (+1), 오른쪽은 (-1) 로 표현할 수 있으며 플레이어는 항상 max 값을 선택한다.
    
  • 3 계층에서 확인해보면 말단 노드들에서 시작하면 해당 노드의 숫자 차이만큼 선공이 이긴다. 
  • 노드5 를 확인해보면 5에서 선공일 경우에는 [+2, -3] 중에서 이기기 위해서 +2 를 선택한다.
  • 노드1 을 확인해보면 -1 이다. 선공이 진다는 뜻이다.
    
    • 실제 플레이를 해보면 선공이 1점을 얻고 후공은 5점을 얻는다. 
    • 이때 후공은 말을 노드8로 내리면 지기때문에 무조건 5로 내린다.
    • 이 말은 후공의 입장에서 노드5에서 얻을 수 있는 최대 점수를 가지기 위해 노력한다는 뜻이다. 
  • 결국 모든 경우에서 서로 최대의 점수를 얻으려고 노력하기에 현재 노드 - 다음 노드 의 값들 중에서 최대 값을 뽑아내면 되고, 그 값이 양수면 선공이 이기고 음수면 후공이 이긴다는 뜻이다.

---

📌 포인트

• 입력을 받아낼 때 아래와 같은 입력도 받아낼 수 있어야한다.
  • 여기서 입력에 대한 에러 표시가 따로 없어 헤맸다.
  • 양방향 트리를 생성한 이후에 단방향 트리로 바꾸어 기존의 코드를 그대로 사용하였다.

4
1 2
3 4
2 3

---

💻 코드

import sys

input = sys.stdin.readline

n = int(input())

def build_tree(n):
    dic = {}
    for _ in range(n - 1):
        u, v = map(int, input().split())
        if u not in dic:
            dic[u] = []
        if v not in dic:
            dic[v] = []
        dic[u].append(v)
        dic[v].append(u)

    tree = {1:[]}
    visited = []
    stack = []
    stack.append(1)
    visited.append(1)
    while stack:
        node = stack.pop()
        for child in dic[node]:
            if child not in visited:
                visited.append(child)
                stack.append(child)
                if node not in tree:
                    tree[node] = []
                tree[node].append(child)
                tree[child] = []
    return tree


tree = build_tree(n)


answer = [0 for _ in range(n + 1)]

def bfs(tree, node):
    for child in tree[node]:
        bfs(tree, child)

    if not tree[node]:
        answer[node] = node
    else:
        maxValue = -1 * sys.maxsize
        for child in tree[node]:
            maxValue = max(maxValue, node - answer[child])
        answer[node] = maxValue

bfs(tree, 1)

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