python 백준 11725번 트리의 부모 찾기

백준 11725번 문제

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

11725번: 트리의 부모 찾기

 

1. 첫번째 접근 방법 노드를 타고 들어가 마지막 노드가 1일경우 값을 return해주어 자신의 상위 노드가 누구인지 확인한다(시간초과)

import sys
sys.setrecursionlimit(100000)

num = int(sys.stdin.readline())
arr = [[] for _ in range(100000)]
loca = [0] * 100000
answer = []
for q in range(num-1):
    a,b = map(int,sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)
    loca[a] = loca[b] = 1
for k in range(100000):
    if loca[k] == 1:
        answer.append(k)
try:
    answer.remove(1)
except:
    pass

def dfs(start,visited):
    visited.append(start)
    ans = None
    for link in arr[start]:
        if ans == None:
            if link not in visited:
            ## 마지막 노드가 1일때까지 탐색 ##
                if link == 1:
            ## 다음 노드가 1이면 현재 노드의 값을 리턴 ##
                    return link
                else:
                    ans = dfs(link,visited)
		## 리턴 값이 있으면 1을 찾았으므로 현재 노드값을 리턴 ##
        if ans > 0:
            return link
    ## 값 출력 ##
    return link

for i in answer:
    visited = []
    print(dfs(i,visited))

2. 2번째 방법 1번 루트 노드부터 찾으면서 내려가 다음 노드를 dfs검색할때 이미 다음노드의 상위 노드가 누구인지를 알 수 있다.

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

num = int(sys.stdin.readline())
arr = defaultdict(list)
ans = {
    1:None
}
for q in range(num-1):
    a,b = map(int,sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)

def dfs(start):
## start가 현재 노드 ##
    for link in arr[start]:
    ## link가 다음깊이탐색할 노드 이며 link노드의 상위노드는 start노드인것을 알 수 있다 ##
        if link not in ans:
        ## link노드의 부모노드가 start인것을 저장 한 후 다음 dfs(다음노드)값을 넣어줌 ##
            ans[link] = start
            dfs(link)

dfs(1)
sort_ans = sorted(ans.items(), key = lambda item: item[0])
for x in sort_ans:
    if x[1] != None:
        print(x[1])

새로 배운 표현 defaultdict

- 호출법 from collections import defaultdict를 통해 호출

- 일반 dict인 경우 값을 넣어줄때 생성된 key값이 없을 경우 error를 반환

arr = dict()
arr[1] = 3
## error 발생 ##

- 하지만 defaultdict 인 경우 

############################defaultdict이 있는 경우###################################
from collections import defaultdict
arr = defaultdict(list) -> 값이 안들어와있으면 리스트로 만들어준다 
arr[1].append(3)

print(arr)
## print ##
{1: [3]}으로 출력 된다

############################defaultdict이 없는 경우###################################
## if not in check 로 같은 효과를 볼 수 있다 ##
arr = dict()

if 1 in arr:
    arr[1].append(3)
else:
    arr[1] = [3]

print(arr)
## print ##
{1: [3]}으로 출력 된다