[백준] 1068번:트리 (Python 파이썬)

[백준] 1068번:트리 (Python 파이썬)

반응형

문제

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

풀이 및 소스코드

dfs로 풀어주었다.

여기서 중요한 점이 삭제할 노드의 부모노드가 가진 자식노드가 삭제할 노드 밖에 없을 때다.

노드를 삭제하면 부모노드가 리프가 되므로 +1을 해줘야 하기 때문.

아래 그림을 보면 쉽게 이해할 수 있다.

이러한 케이스에서 올바른 출력을 하기 위해서,

dfs가 끝난 후 만약 삭제할 노드의 부모노드가 가진 자식노드의 개수가 하나 뿐이라면

ans에 +1을 해주었다.

import sys input = sys.stdin.readline sys.setrecursionlimit(10000) def dfs(x): global ans if (x not in arr and x != del_node): ans+=1 return else: for i in range(n): if(arr[i]==x and i!=del_node): dfs(i) return ans n = int(input()) arr = list(map(int, input().split())) del_node = int(input()) start = arr.index(-1) ans = 0 if(start == del_node): print(ans) else: dfs(start) if (arr.count(arr[del_node])==1): ans+=1 print(ans)

반응형

from http://jainn.tistory.com/172 by ccl(A) rewrite - 2021-08-02 23:00:18