문제를 푸는 기준

주어진 트리 표현을 익숙한 구조로 바꿉니다. 부모 배열이라면 자식 목록을 만들고, 무방향 간선이면 부모로 돌아가는 간선을 제외합니다.

핵심 개념

대표 문제

조직도의 최대 깊이

parent[i]가 i번 노드의 부모인 배열 parent가 주어집니다. 루트 부모는 -1이고 루트 깊이는 0일 때 최대 깊이를 반환하세요.

함수 시그니처: solution(parent)

제한사항

• 노드 수는 1 이상 200,000 이하입니다.
• 정확히 하나의 루트가 있는 올바른 트리입니다.

입출력 예

풀이 설계

1. parent를 보며 자식 목록과 루트를 찾습니다.
2. 스택에 루트와 깊이를 넣습니다.
3. 정점을 꺼내 최대 깊이를 갱신하고 자식을 넣습니다.

JavaScript 풀이

function solution(parent) {
  const children = Array.from({ length: parent.length }, () => []);
  let root = -1;
  for (let node = 0; node < parent.length; node += 1) {
    if (parent[node] === -1) root = node;
    else children[parent[node]].push(node);
  }
  const stack = [[root, 0]];
  let maxDepth = 0;
  while (stack.length > 0) {
    const [node, depth] = stack.pop();
    maxDepth = Math.max(maxDepth, depth);
    for (const child of children[node]) stack.push([child, depth + 1]);
  }
  return maxDepth;
}

복잡도

• 시간복잡도: O(n)
• 공간복잡도: O(n)
• 핵심 패턴: 부모 배열을 자식 목록으로 바꾼 뒤 깊이 순회
• 경계 사례: 루트 하나뿐이면 깊이 0 반환

연습 문제

1. 리프 개수

자식이 없는 노드 개수를 반환하세요.

2. 서브트리 크기

각 노드의 서브트리 크기를 반환하세요.

3. 공통 조상

두 노드의 가장 가까운 공통 조상을 반환하세요.

자주 하는 실수

• 루트 깊이 정의를 확인하지 않는 실수
• 무방향 트리에서 부모로 되돌아가는 실수
• 노드가 많아도 깊은 재귀만 사용하는 실수
• 후위 계산을 전위 시점에 하는 실수

핵심 정리

• 함수 시그니처와 반환 자료형을 먼저 확정합니다.
• 제한사항으로 가능한 시간복잡도를 판단합니다.
• 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
• 완성한 solution 함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.

확인 문제

참고 자료

• Princeton Algorithms 4e - Graphs 
• MIT OpenCourseWare 6.006 Introduction to Algorithms 
• MDN Array