오랜만에 블로그에 알고리즘 풀이를 올려본다. 한동안 문제는 조금씩 풀었지만 난이도가 리뷰하기 애매한경우도 있어서 오랜만에 글 올려본다.
최근들어 코테를 계속 도전중인데 요즘 추세가 그런지 킬러로 계속 트리가 나온다. 특히 binary tree 구조가 나오는데 시험에서는 항상 input data로 2n개수의 리스트를 보통 준다. 그걸로 경기를 하는 느낌의 문제가 나오는데 최근 skt fly 부트캠프에 지원하면서 킬러문제로 complete binary tree가 나왔지만 결국 못풀었다ㅠ 그래서 요즘 트리를 제대로 연습중이다.
어제 한번 데이면서 깨달은 방식은 입력받을 때 dictinary구조에 부모 자식 관계 없이 각 key와 value에 숫자를 넣어서 두 node가 연결된 상태를 만든 후 visit list만 있으면 트리 구조 대로 탐색이 가능하다.
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
input_list = list(map(int, input().split()))
tree = dict()
visit = [False]*N
root = 0
answer = 0
def bfs(root):
dq = deque([root])
global answer
while dq:
n = dq.popleft()
for i in tree[n]:
if not visit[i]:
dq.append(i)
visit[i] = True
number = 0
for j in tree[i]:
if visit[j]:
number += 1
if number == len(tree[i]):
answer += 1
for idx, val in enumerate(input_list):
if val == -1:
root = idx
else:
if idx in tree:
tree[idx].append(val)
else:
tree[idx] = [val]
if val in tree:
tree[val].append(idx)
else:
tree[val] = [idx]
visit[root] = True
erase_num = int(input())
visit[erase_num] = True
if erase_num == root:
print(root)
elif sum(visit) == N:
print(1)
else:
bfs(root)
print(answer)defaultdict를 쓰면 더 빠른 입력 받는 코드를 쓸 수 있겠지만 나는 아직까지 그냥 저렇게 if else문으로 나눠서 입력받는게 편하다.
이 문제는 root가 0번째 node가 무조건 root 인 것 같은데 난 혹시나 -1을 받을 때 root 값을 받도록 했다.
지운 노드는 당연히 그 노드를 방문처리 해주면 지우는 거랑 똑같고...
문제는 leaf node를 어떻게 분간하냐 인데 나는 그 노드와 연결된 다른 노드들이 모두 방문 처리가 되었을 때 그때 leaf node라고 판단했다.
문제는 한번 틀렸는데... 99% 일때 틀렸다.
예외를 밑에서 처리해서 맞췄는데 솔직히 약간 찝찝하긴 하다.
예외는 0과 1 node 두개중 1을 제거했을 때 답인데... 루트 노드가 leaf node라서 답이 1이다.
예외처리를 했는데 이렇게 안하고 로직을 더 잘 짰으면 아마 통과되었을까 싶기는 하다... 일단 로직을 고치기 귀찮아서 예외처리로 답을 맞췄다.
tree를 linked-list 형태로 쓰지 않는 것이 확실히 편하다. 그렇지만 앞으로 코테 대비 어떤 형태의 tree data structure을 만들어 문제를 해결해 나아갈지 고민해 보겠다.
