파이썬 알고리즘 187번 | [백준 15900번] 나무 탈출 -DFS

187. 나무 탈출

1) 어떤 전략(알고리즘)으로 해결?

• dfs 로 루트로부터 노드들 사이의 거리 구해준다
• 이후 리프노드들과 루트 노드 사이의 거리들을 모두 합해준 뒤 홀짝 여부 판별

2) 코딩 설명

<내 풀이>

import sys
sys.setrecursionlimit(10**5)
# sys.setrecursionlimit(10**9) : 로 하면 에러난다.

n = int(sys.stdin.readline().rstrip()) # 노드의 갯수 

node = [[] for _ in range(n+1)] # 1부터 시작
dis = [0 for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

def dfs(num) : # 각 노드들과 루트 노트(1) 사이의 거리 구하는 dfs
        visited[num] = 1
        for child in node[num] :
            if visited[child]==0 :
                dis[child] = dis[num]+1
                dfs(child)

for i in range(n-1) : 
    a, b= map(int, sys.stdin.readline().rstrip().split())
    node[a].append(b) ; node[b].append(a)

dfs(1) # 루트  노드부터 -> 이 친구와 다른 노드 사이의 측정 위해

total = 0
possible = False

for j in range(2, len(node)) :
    if(len(node[j])==1) :
        total+=(dis[j]) # 리프에서 루트까지의 총 거리 구함 

# 리프에서 루트까지 가는 총거리가 홀수면, 
# 짝수번때 형석은 말이 없으니 지게 됨

if (total%2==1) : print("Yes") 
else : print("No")

<내 틀렸던 풀이, 문제점>

import sys

def dfs(leaf, cnt) :
    global find
    if find == True:
        return
    if leaf == 0 :
        print(cnt)
        if cnt%2==1:
            find = True
            return
        else : 
            find = False

    else :
        
        for parent in node[leaf] : 
            cnt+=1
            dfs(parent, cnt)
            cnt-=1


n = int(sys.stdin.readline().rstrip())
node = [[] for _ in range(n)]
leaf =[[] for _ in range(n)]

for i in range(n-1) :
    a,b = map(int, sys.stdin.readline().rstrip().split())

    if(a<b) :
        node[b-1].append(a-1) # 자신의 부모 담음 
        leaf[a-1].append(b-1)
    else : 
        node[a-1].append(b-1) 
        leaf[b-1].append(a-1)

print(leaf, node)
for k in range(len(leaf)) :
    if len(leaf[k])==0: # 자식이 없으면 리프노드 
        cnt = 0 # cnt가 홀수라면 상원이가 이긴다
        find = False
        dfs(k, cnt)
        
if(find==True)  : print("Yes")
else : print("No")

메모리 초과

import sys
sys.setrecursionlimit(10**9)

n = int(sys.stdin.readline().rstrip())
node = [[] for _ in range(n+1)] # 1부터 시작
possible = False

def dfs(num) :
    global possible
    if possible == True :
        return

    if visited[1]==1 :
        if(dis[1]%2==1) : possible = True
        return

    else : 
        visited[num] = 1
        for parent in node[num] :
            if visited[parent]==0 :
                visited[parent]=1
                dis[parent] = dis[num]+1
                dfs(parent)
                visited[parent]=0
                dis[parent]-= (dis[num]+1)

for i in range(n-1) :
    a, b= map(int, sys.stdin.readline().rstrip().split())
    node[a].append(b) ; node[b].append(a)

# node 에서 leaf 는 간선이 단 하나인 것 뿐
for j in range(1, len(node)) :
    if(len(node[j])==1) :
        dis = [0 for _ in range(n+1)]
        visited = [0 for _ in range(n+1)]
        dfs(j)

if (possible) : print("Yes")
else : print("No")

<반성 점>

<배운 점>