[백준] 15900번, 나무 탈출 (Python)

문제

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

15900번: 나무 탈출

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

n = int(input())

answer = 0
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
distance = [0 for _ in range(n+1)]
for i in range(n-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(cur):
    visited[cur] = True
    for next in graph[cur]:
        if visited[next] == False:
        	# distance에는 루트노드부터 모든 노드까지에 거리를 갱신해준다.
            distance[next] = distance[cur] + 1 
            dfs(next)

dfs(1)

# 리프노드를 찾아줌
for i in range(2,n+1):
    if len(graph[i]) == 1:
        answer += distance[i]

if answer % 2 == 0:
    print("No")
else:
    print("Yes")

루트노드에서 dfs 탐색을해 모든 노드까지에 거리를 distance 배열에 저장해준다.

 

게임말이 리프노드에서 루트노드까지 올라가니까 루트노드에서 모든 리프노드까지에 거리를 더해주면 된다.

리프노드는 연결된 노드가 한개밖에 없으면 리프노드로 보면된다. 루트노드는 제외이기 때문에 for문은 2부터 돌아준다.

 

게임을 성원이부터 시작하기 때문에 answer값이 짝수일 경우 No, 홀수이면 Yes를 출력한다.

 

python3는 시간초과가 떠서 pypy로 제출했다.

맨처음에는 재귀 깊이를 sys.setrecursionlimit(10**6)으로 해줬는데 pypy에서 메모리초과가 나서

sys.setrecursionlimit(10**5)로 바꿔줬더니 통과하였다.