문제 바로가기
문제:
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다.
입력:
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
출력:
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
풀이:
틀린 풀이 1.
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N = int(input())
graph = [[] for _ in range(N)]
lst =list(map(int,sys.stdin.readline().split(" ")))
for node,i in enumerate(lst[1:],start = 1):
graph[node].append(i)
graph[i].append(node)
x = int(input())
Q = deque([x])
# 삭제할 노드
while Q:
now = Q.popleft()
for i in graph[now]:
if i > now:
Q.append(i)
graph[now] = False
res = 0
for i in graph:
if i != False and len(i) == 1:
res += 1
print(res)
내 아이디어는 양방향 그래프로 만들어주고
삭제할 노드를 Q로 받아온다.
그리고 Q노드의 연결된 간선들을 하나씩 뽑는데 자식노드들만 삭제해야하므로 그 값보다 큰 값들만 뽑아와서 Q에 더해주고
지금 노드를 False로 바꿔주었다.
리프노드인 것은 연결된 노드가 1개 밖에 없어서 False (삭제된노드) 가 아니면서 선이 1개 일 경우를 뽑아 왔는데
예제는 다 맞지만 틀린다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N = int(input())
lst = list(map(int, sys.stdin.readline().split()))
K = int(input())
def dfs(k,lst):
lst[k] = 1e9
for i in range(len(lst)):
if k == lst[i]: # 어떤숫자의 부모가 k 이면 잘라야함
dfs(i,lst)
dfs(K, lst)
count = 0
for i in range(len(lst)):
if lst[i] != 1e9 and i not in lst: # 1e9 가 아니면서, 부모노드가 아님
count += 1
print(count)lst에는 해당 노드의 부모가 들어있다.
즉 k 노드를 없앤다는것은 부모가 k노드인 것을 삭제하면 된다는 것이다. dfs 탐색으로 찾아준다.
어떤 숫자의 부모가 k이면 삭제해주는것이다.
만약 4를 삭제해준다 하고 4에 리프가 5,6 이면
k = 4, lst[i] = 5 이거나 6인 값은 부모가 4 가 나오므로
dfs(5,lst) 로 재귀를 또 호출해 lst[k] = 1e9로 자르게 된다.
댓글