[백준] 15900 나무 탈출

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

재귀를 이용하여 모든 리프 노드에서 루트 노드까지의 거리를 구한 후, 모두 더한 값을 구하였습니다.

모든 리프 노드의 더해진 값이 짝수인지 홀수인지 여부에 따라 이길 수 있는지 없는지 구하였습니다.

2) 알고리즘

• 재귀
• 트리

3) 풀이 코드

사용 언어 - Python

import sys
sys.setrecursionlimit(1000000)
sys.stdin = open('input.txt')

def solution(node):
    global need_move
    
    is_leaf = True                                  # 현재 노드가 리프노드인지 구분을 위함
    for next in linked[node]:
        if not distance[next]:                      # 방문하지 않은 노드들이라면
            distance[next] = distance[node]+1       # 현재 노드까지 거리 갱신
            solution(next)                          # 재귀 호출
            is_leaf = False                         # 다음 노드를 탐색하므로 리프 노드가 아님
    
    if is_leaf:                                     # 리프 노드라면
        need_move += distance[node] - 1             # 게임말 이동이 필요한 칸 수 추가

N = int(sys.stdin.readline())                       # 노드의 개수
linked = [[] for _ in range(N+1)]                   # 연결 관계
distance = [0] * (N+1)                              # 노드들 거리
need_move = 0                                       # 게임말들이 이동이 필요한 턴의 수

for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().split())   # 노드들 양방향 연결 관계 추가
    linked[a].append(b)
    linked[b].append(a)

distance[1] = 1                 # 1번 노드의 시작을 거리 1로 설정
solution(1)                     # 노드 탐색

if need_move % 2:               # 홀수라면 이김
    print('Yes')
else:                           # 짝수라면 이길 수 없음
    print('No')

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/15900

15900번: 나무 탈출

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다