백준 / 1068번 트리 -dfs / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 1068번 트리

문제 사이트: https://www.acmicpc.net/problem/1068

1068번: 트리

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

44973

12703

9717

28.123%

문제

 

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

예제 입력 1 복사

5
-1 0 0 1 1
2

예제 출력 1 복사

2

예제 입력 2 복사

5
-1 0 0 1 1
1

예제 출력 2 복사

1

예제 입력 3 복사

5
-1 0 0 1 1
0

예제 출력 3 복사

0

예제 입력 4 복사

9
-1 0 0 2 2 4 4 6 6
4

예제 출력 4 복사

2

출처

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: cmmcme, djm03178, wookje

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 깊이 우선 탐색

---

나의 풀이

leaf = 0
def dfs(idx,tree):
    global leaf
    if idx in tree and tree[idx]:
        for i in tree[idx]:
            dfs(i,tree) # DFS 함수 호출
    else:
        if idx != -1:
            leaf += 1
if __name__ == "__main__":
    n = int(input())
    uptree = list(map(int,input().split())) # 상위 부모 트리에 대한 정보
    rnum = int(input()) # 없앨 트리의 인덱스

    tree_dict = {i:[] for i in uptree}

    for i in range(len(uptree)):
        tree_dict[uptree[i]].append(i)

    tree_dict[uptree[rnum]].pop(tree_dict[uptree[rnum]].index(rnum)) # 없앨 인덱스의 트리 끊기
    dfs(-1,tree_dict)
    print(leaf)

처음에 함수 안에서         if idx != -1: 를 안넣어줘서 틀렸었다.

루트를 자르면 잎이 모두 날라가는거니까.. leaf 잎도 남아있으면 안된다.

그래서 해당 케이스만 잘 확인하고 구현하면 DFS 로 쉽게 풀림

 

---