문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.
문제 유형 보기
https://www.acmicpc.net/problem/1068
풀이
1차 시도) 실패
테케는 다 맞았는데… 더 고민해보자.
import sys
input = sys.stdin.readline
# 노드 하나 지운 이후의 트리의 리프 노드 개수를 구하라.
# 노드를 지우면 그 노드에 딸린 서브트리가 통째로 지워짐.
# 입력 : 노드 개수, 0~n-1번 노드까지의 각 노드의 부모, 지울 노드의 번호
# 출력 : 처리 이후 리프 노드의 개수
# 흠... 이거 오름차순으로 주나?
# 일단, 결국 그 노드를 기준으로 후위 순회 돌리면 되겠는데?
# 후위 순회의 action은, 자신의 자식 노드를 전부 -1로 하는 것.
# 그리고 마지막에 루트 노드를 -1로.
n = int(input())
tree = [[-1, -1] for _ in range(n)]
parents = list(map(int, input().split()))
for i in range(1, n):
if tree[parents[i]][0] == -1:
tree[parents[i]][0] = i
continue
tree[parents[i]][1] = i
# print(tree)
# [[1, 2], [3, 4], [-1, -1], [-1, -1], [-1, -1]]
del_node = int(input())
def postorder(node):
if node == -1:
return
postorder(tree[node][0])
postorder(tree[node][1])
tree[node] = [-2, -2]
postorder(del_node)
counts = 0
for children in tree:
for i in range(2):
if children[i] == del_node:
children[i] = -1
if children.count(-2) != 2:
if children.count(-1) + children.count(-2) == 2:
counts += 1
# del_node는 리프 노드로 간주되어 세어졌을 것이니
print(counts)2차 시도) 실패
이거… 트리 정렬해버리면 index를 잃어버림. 어카지…
게다가, 이진 트리가 아닐 수도 있다!
import sys
input = sys.stdin.readline
# 노드 하나 지운 이후의 트리의 리프 노드 개수를 구하라.
# 노드를 지우면 그 노드에 딸린 서브트리가 통째로 지워짐.
# 입력 : 노드 개수, 0~n-1번 노드까지의 각 노드의 부모, 지울 노드의 번호
# 출력 : 처리 이후 리프 노드의 개수
# 흠... 이거 오름차순으로 주나?
# 일단, 결국 그 노드를 기준으로 후위 순회 돌리면 되겠는데?
# 후위 순회의 action은, 자신의 자식 노드를 전부 -1로 하는 것.
# 그리고 마지막에 루트 노드를 -1로.
n = int(input())
tree = [[-1, -1] for _ in range(n)]
parents = list(map(int, input().split()))
# print(tree)
# [[1, 2], [3, 4], [-1, -1], [-1, -1], [-1, -1]]
del_node = int(input())
for i in range(1, n):
if tree[parents[i]][0] == -1:
tree[parents[i]][0] = i
continue
tree[parents[i]][1] = i
is_del_node = [[0] for _ in range(n)]
is_del_node[del_node] = 1
parents = list(zip(parents, is_del_node))
parents.sort(key = lambda x: x[0])
def postorder(node):
if node == -1:
return
postorder(tree[node][0])
postorder(tree[node][1])
tree[node] = [-1, -1]
if tree[parents[node]][0] == node:
tree[parents[node]][0] = -1
else:
tree[parents[node]][1] = -1
parents[node] = -2
postorder(del_node)
counts = 0
for index in range(n):
if parents[index] != -2:
if tree[index].count(-1) == 2:
counts += 1
# del_node는 리프 노드로 간주되어 세어졌을 것이니
print(counts)250225 재시도
3차 시도, 시도 중 모르겠어서 질문게시판 보고 수정해 성공
질문게시판에서 2가지 유형의 엣지 케이스 확인
https://www.acmicpc.net/board/view/132447
내 풀이는, 지워야 할 노드를 루트 노드로 같는 서브 트리를 dfs(와 유사한 방식으)로 탐색하며, 지워가고 있음.
여기서 dfs는 그냥 ‘그 서브트리를 통째로 지워버리는’ 역할만 함.
여기서 지움당하는 대상은 parents로 구현된 트리 그 자체. parents를 바꿔나가는 거임.
잊지말자!! 트리의 구현 방식은 여러가지가 있다구!!
‘parents[자식트리번호] = 부모트리번호’로 트리를 표현하는 테크닉!! 기억하자.
이거 근데 dfs라고 쓰긴 썼는데, 사실 트리 (후위) 순회에 더 가깝긴 한듯.ㅋㅋ
그리고 전위를 하냐 후위를 하냐 중위를 하냐는 여기선 아무 상관이 x
import sys
input = sys.stdin.readline
# 특정 노드를 제거한 후의 리프 노드의 개수를 세자
# 입력 : 트리의 노드 개수 n, 둘째 줄부턴 0 - n-1 번 노드까지 각 노드의 부모 주어짐
# 셋째 줄에는 지울 노드 번호
n = int(input())
parent = list(map(int, input().split()))
t = int(input())
root = parent.index(-1)
# 지우는 건 둘째치고, 리프 노드 개수를 어떻게 셀 수 있지?
# 지우는 거는 뭐 그 노드를 부모로 가지는 노드들을 -1로 값 바꿔주면 되지 않을까?
# 탐색하면서, 그 노드의 값이 parent에 없으면 리프 노드다? 이거 괜찮아보이는데?
# 일단 n이 50 이하인데, 좀 비효율적이어도 될 듯함.
# while 돌면서 flag 설정해두고, 순차적으로 다 지우면 될 듯한데?
# 어? dfs? bfs?
def dfs(node):
for i in range(n):
if parent[i] == node: # 만약 i가 node를 부모로 가지면
dfs(i) # i 기준으로 다시 dfs 돌림
parent[node] = -1
dfs(t)
counts = 0
# 루트 노드 혼자 남았거나, 아님 루트 노드를 지워버렸을 경우
if parent.count(-1) == n:
if t != root: # 루트 노드를 지웠을 경우
counts = 1
n = 0 # 뒤에 오는 반복문 실행 안되게 처리
for i in range(n):
if parent[i] != -1 and i not in parent:
counts += 1
print(counts)
# (모르겠음 -> 질문 게시판 확인)
# 루트 노드 하나만 남아도 리프 노드가 됨을 간과.
'''
2
-1 0
1
output: 0
answer: 1
'''
# 루트 노드 하나만 남았다는건, 모든 노드가 다 -1이라는 거임.
# 위 문제 해결해도 99%에서 오류 나옴...
# 루트 노드를 삭제하면 0이 나와야 함을 간과.
'''
2
1 -1
1
output: 1
answer: 0
'''강사님 정답 코드 확인
일단 우리가 알던 대로 트리를 만드는데, 거기에 ‘지울 노드’는 존재하지 않는, 즉 끊겨있는 트리를 넣음!!
정확히는, 그 지울 노드의 부모 노드에다가 그 지울 노드를 넣는 행위를 생략해버린 것!!
그렇게 한 후에 루트 노드에서 dfs 돌리면, 끊긴 노드는 제외하고 탐색하니까, 노드를 버린 것과 동일한 효과!!
와… 이 아이디어를 어떻게 떠올리지?
=> 일단 경험치로 가지고 가자!!
근데, 솔직히 이 문제는 내 풀이(위에 3차 시도)로 순회로 푸는 게 더 나아보이기도 함.
enumerate 사용한 건 굳이같기도 함. 그냥 parents[index] ← parent 로 대체 가능.(enumerate 사용이 더 직관적이긴 함)
이건 순수 dfs가 되므로, 내부에서 leafs를 바로바로 변동시킬 수 있음. 물론 leafs를 직접 세는 코드를 외부에 구현할 수도 있지만(아마 이렇게 하면, [-1, -1]인 것중에, 그 놈을 자식으로 가지는 놈이 있으면 → leafs += 1 하면 될듯), 바로바로 업데이트가 되는데 굳이?
import sys
input = sys.stdin.readline
def dfs(node):
# 리프 노드인 경우
if not tree[node]:
return 1
leafs = 0
for next_node in tree[node]:
leafs += dfs(next_node) # 자식 노드들을 탐색하며 리프 노드의 개수 더하기
return leafs
# return sum(dfs(next_node) for next_node in tree[node])
n = int(input())
parents = list(map(int, input().split()))
target = int(input()) # 삭제할 노드
# 트리 만들기 (트리가 이진트리가 아닐 수 있음에 주의!)
tree = [[] for _ in range(n)]
for child, parent in enumerate(parents):
if parent == -1:
root = child # 루트 노드 찾기
continue
if child == target:
continue # 삭제할 노드는 트리에 포함하지 않음
tree[parent].append(child)
if target == root:
print(0) # 루트 노드를 삭제하는 경우 0 출력
else:
print(dfs(root))추가로, 이 문제는 궁금해서 이후 다른분들 풀이도 많이 찾아봤는데,
내 3차 시도처럼 푸신 분들도 계시고, 강사님 풀이처럼 우리가 해오던 트리 표현 방식으로 푸신 분들도 계셨다.
내 풀이처럼 푼 분은 이 분이 비슷했다.
아래 분은 내 풀이랑 방식은 같은데, dfs(겸 순회)가 아닌 bfs를 하셨다. bfs도 충분히 가능!
https://www.acmicpc.net/source/90242839
그리고, 강사님 정답 풀이와는 아래 분 풀이가 비슷했다.
https://velog.io/@ice-prince/백준-1068-트리-Python
5차 시도) 위 블로그 글 보고, 3차 시도에서 추가 수정
그냥 ‘지웠음’ 표시를 -1이 아닌, -2, -3 따위의 magic number로 처리하면 되는 문제였음!!!!!
아!!!!!!!!!!!!!!!!
이제 루트 노드 관련 엣지 케이스 다 대응가능. ㅎㅎ
import sys
input = sys.stdin.readline
# 특정 노드를 제거한 후의 리프 노드의 개수를 세자
# 입력 : 트리의 노드 개수 n, 둘째 줄부턴 0 - n-1 번 노드까지 각 노드의 부모 주어짐
# 셋째 줄에는 지울 노드 번호
n = int(input())
parent = list(map(int, input().split()))
t = int(input())
# 지우는 건 둘째치고, 리프 노드 개수를 어떻게 셀 수 있지?
# 지우는 거는 뭐 그 노드를 부모로 가지는 노드들을 -1로 값 바꿔주면 되지 않을까?
# 탐색하면서, 그 노드의 값이 parent에 없으면 리프 노드다? 이거 괜찮아보이는데?
# 일단 n이 50 이하인데, 좀 비효율적이어도 될 듯함.
# while 돌면서 flag 설정해두고, 순차적으로 다 지우면 될 듯한데?
# 어? dfs? bfs?
def dfs(node):
for i in range(n):
if parent[i] == node: # 만약 i가 node를 부모로 가지면
dfs(i) # i 기준으로 다시 dfs 돌림
parent[node] = -2
dfs(t)
counts = 0
for i in range(n):
if parent[i] != -10 and i not in parent:
counts += 1
print(counts)'Algorithms and Languages > 파이썬 알고리즘 문제풀이' 카테고리의 다른 글
| [Python/프로그래머스] 42626. 더 맵게 (0) | 2025.02.26 |
|---|---|
| [Python/DailyAlgo, 백준] 92. 우선순위 큐, 11279. 최대 힙, 11286. 절댓값 힙 (0) | 2025.02.26 |
| [Python/백준] 20364. 부동산 다툼 (0) | 2025.02.25 |
| [Python/백준] 1991. 트리 순회 (0) | 2025.02.25 |
| [Python/DailyAlgo] 94, 95, 96. 트리 전위, 중위, 후위 순회 (0) | 2025.02.24 |