백준) 1068 트리
코드
n = int(input())
li = list(map(int, input().split()))
r = int(input())
tree = [[]for _ in range(n)]
root = 0
ans = 0
for idx, i in enumerate(li):
if i == -1:
root = idx
continue
if idx == r:
continue
tree[i].append(idx)
def dfs(v):
global ans
if len(tree[v]) ==0:
ans += 1
return
for i in tree[v]:
dfs(i)
if root != r:
dfs(root)
print(ans)
접근방법
- 트리를 구현한다.
- 애초에 부모를 주어준다고 명시되어 있기때문에 양방향으로 저장할 필요가 없다.
- 각 부모별로 자식을 저장하는데 지워야되는 노드는 추가하지 않는다.
- 그다음 트리를 순회하면서 자식노드가 없는애들일때마다 답을 1씩 증가시켜주면 된다.
챙겨갈점
- 부모노드를 줄땐 굳이 양방향으로 저장하지 않아도 되고
- 그러므로 방문한 노드를 저장하는 배열도 필요없을듯.
- 근데 조건을 좀 잘봐야될듯 싶다.
Author And Source
이 문제에 관하여(백준) 1068 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@bokman/백준-1068-트리
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
n = int(input())
li = list(map(int, input().split()))
r = int(input())
tree = [[]for _ in range(n)]
root = 0
ans = 0
for idx, i in enumerate(li):
if i == -1:
root = idx
continue
if idx == r:
continue
tree[i].append(idx)
def dfs(v):
global ans
if len(tree[v]) ==0:
ans += 1
return
for i in tree[v]:
dfs(i)
if root != r:
dfs(root)
print(ans)
- 트리를 구현한다.
- 애초에 부모를 주어준다고 명시되어 있기때문에 양방향으로 저장할 필요가 없다.
- 각 부모별로 자식을 저장하는데 지워야되는 노드는 추가하지 않는다.
- 그다음 트리를 순회하면서 자식노드가 없는애들일때마다 답을 1씩 증가시켜주면 된다.
챙겨갈점
- 부모노드를 줄땐 굳이 양방향으로 저장하지 않아도 되고
- 그러므로 방문한 노드를 저장하는 배열도 필요없을듯.
- 근데 조건을 좀 잘봐야될듯 싶다.
Author And Source
이 문제에 관하여(백준) 1068 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@bokman/백준-1068-트리
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여(백준) 1068 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bokman/백준-1068-트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)