[백준 - Python] 1068. 트리 (DFS/BFS)

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

1068번: 트리

 

코드

n = int(input())
node = list(map(int, input().split()))
del_node = int(input())

def dfs(v):
    node[v] = -2
    for i in range(n):
        if node[i] == v:
            dfs(i)

dfs(del_node)

cnt = 0
for i in range(n):
    if node[i] != -2 and i not in node:  # i 노드가 지워지는 노드가 아니고 && 자식이 트리 안에 없으면(어떠한 노드에 대해서도 부모 노드가 아니면 리프 노드임) 카운팅
        cnt += 1

print(cnt)

 

 

문제를 처음 읽고는

0번 노드부터 (N-1)번 노드까지 순차적으로 들어오기 때문에

들어오는 대로 graph 리스트에 해당하는 노드에 연결 노드를 저장을 하고

삭제하려는 노드를 그래프에서 제거해준 다음에(연결을 제거)

전체 노드를 순회하면서 -1로 루트 노드를 갖는 경우에

해당 노드를 기준으로 DFS 탐색을 하면서 말단 노드를 세어주면 되겠다고 생각했고,

그대로 구현을 했다.

 

백준 주어진 예시는 다 통과가 되는데,

제출이 통과가 안되는데, 왜 틀리는 건지 모르겠다.

(나중에 다시 확인해봐야겠다.)

 

다른 분들의 코드를 참고했는데,

삭제할 노드로 dfs를 시작해서,

dfs 내에서 노드 개수만큼 반복문을 돌면서 각 노드에 접근하여, 부모가 삭제되는 노드이면 자식도 삭제해줘야 함으로

dfs 재귀를 실행하여 같이 지워주는 방식으로 구현을 하셨다.

 

그 후에 다시 노드의 개수만큼 반복문을 돌면서,

노드가 지워지는 노드가 아니면서, 즉 -2가 아니면서

노드 리스트 안에 없으면, 즉 노드 리스트 안에 없다는 것은 어떤 노드의 부모가 되지 않는 노드라는 말이고,

다른 말로 말단 노드라는 뜻이므로

카운팅을 해주고

최종 카운팅을 출력해주었다.

 

생각을 좀만 더 하면 간결한 코드로 문제가 풀린다.

문제를 많이 풀고 연습 많이 하기 !