Notion에서 작성한 글이라, 여기 에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 뉴스 전하기

[뉴스 전하기]

• 대충 트리가 뭐다~ 정도만 아는 상태라, 일단 오늘 문제는 스킵했다가 나중에 공부를 하고 풀어야겠다고 생각했다. 그런데 “Challenger” 문제라 그런 것인지 괜히 도전해보고 싶었다(?). 😓

• 정말 몇 시간동안 파고들었지만 끝끝내 WA…

• 결국엔 틀린 일기나 다름없는 오늘의 글을 TIL이랍시고 작성하기 굉장히 부끄럽긴 하지만, 코드를 계속해서 고쳐나가면서 트리를 여러 방법으로 표현해 봤고, 비교 기준 설정, 재귀, 유사 DFS까지 도달하는 과정을 기록하고 싶어서 (철판을 깔고) 올리게 되었다.

• 다시 한 번 처음부터 푸는 마음으로 넓게 보고 왜 틀렸는지, 어디에서 어떤 부분이 논리적으로 잘못됐는지 재차 검토해 보아야 겠다.

• 트리 표현하기

  • 사실 어떤 방법이 좋은 방법인지 아직 모른다. 맨 처음엔 어디서 본 건 있어가지고 클래스로 구현해보려고 했는데, 며칠 전에 배운 그래프를 adjacency list로 나타내는 방법이 떠올랐다.
  • 그렇게 adjacency list로 표현을 해 봤는데, 지금와서 생각해 보면 어차피 연결 요소는 adjacency list도 $O(1)$에 찾을 수 있는데 defaultdict가 떠올랐고 defaultdict로 구현했다.
  • 아마 하나하나 그려보다 보니 sparse한 형태의 트리에서 dictionary를 이용하는 방법이 메모리도 절약하고 나중에 언젠가(?) 요소들을 다룰 때 혹시나 시간복잡도 면에서 유리하진 않을까 싶어서 그랬던 것 같다.

• 비교 기준 설정

  • 처음에는 가장 많은 leaf node를 가진 부모 노드의 자식 수 - 1부터 시작해서,,,
  • depth + 자식 수, …
  • 분기 시 자식 노드들 중 가장 depth가 깊은 값 기준으로 정렬 등등 수많은 시행착오를 겪었다.
  • 지금 와서 돌아보니 조금씩 틀렸지만 조금씩 개선해 나가며 정답에 근접해가고 있었던 것 같다. 마지막 TC에서 틀리고 “매 순간 어느 자식노드부터 전달하는 게 최적인지의 기준을 어떻게 설정해줘야 할지”를 꽤 오래 고민했다.

• 재귀

  • 매 순간 어느 자식노드부터 전달하는 게 최적인지의 기준을 어떻게 설정해줘야 할지를 고민하다가, 전달의 우선순위를 고려하지 않은 전달 시간을 통해 구한 자식 노드 중 가장 오래 걸리는 시간을 기준으로 정렬하기 위해 바로 아래에 있는 자식 노드가 아닌 subtree 느낌의 모든 자식 노드를 구할 필요가 있었다.
  • 이를 위해 각 자식에 대해 재귀적으로 접근할 필요를 느꼈고, 재귀가 익숙하지 않아 지금 보면 간단하지만 extend_child를 짜는 데에 꽤 걸렸던 것 같다. 재귀 연습은 추가로 꼭 꼭 해야겠다.

• 유사 DFS

  • 각 노드를 순회하며 전달 시간을 갱신해야겠다고 생각하여 DFS 비스무리한 코드를 짰다. tree dictionary 특성상 어차피 아래로만(부모로 올라가지 않고 자식으로 내려가는) 순회가 진행될 수밖에 없기 때문에 visited와 같은 리스트는 만들지 않았다.

Wrong Answer.

from collections import defaultdict

def extend_child(node):
    ret = []
    child = tree.get(node, [])

    for c in child:
        ret.append(c)
        ret.extend(extend_child(c))
    
    return ret

n = int(input())
emp = [*map(int, input().split())]

tree = defaultdict(list)
depth = [0]
for i in range(1, n):
    tree[emp[i]].append(i)
    depth.append(depth[emp[i]]+1)

times = [depth[i] + sum(not tree[c] for c in tree[i]) for i in range(n)]
# print(f'전달 우선순위를 고려하지 않은 전달 시간 : {times}')

# print(depth)
stack = [0]

while stack:
    cur = tree[stack.pop()]
    if cur:
        child = sorted(cur, key=lambda x: max((times[c] for c in extend_child(x)), default=50))
        for i in range(len(child)-1, 0, -1):  # 전달 시간 갱신
            depth[child[i]] += 1
            for c in extend_child(child[i]):
                times[c] += i
            # print(f'depth updated : {depth[:10]}, {depth[10:20]}, {depth[20:]}')
        stack.extend(child)

# print(depth)
print(max(depth))