문제를 푸는 기준

그룹 병합과 연결 여부가 반복되면 유니온 파인드, 선행 조건을 만족하는 순서가 필요하면 위상 정렬을 사용합니다.

핵심 개념

대표 문제

가능한 작업 순서

작업 수 n과 [before,after] 선행 관계 dependencies가 주어집니다. 가능한 작업 순서 하나를 반환하고 사이클이면 빈 배열을 반환하세요.

함수 시그니처: solution(n, dependencies)

제한사항

• n은 1 이상 200,000 이하입니다.
• 중복 간선은 없습니다.

입출력 예

풀이 설계

1. 인접 리스트와 진입차수를 만듭니다.
2. 진입차수 0 작업을 큐에 넣습니다.
3. 작업을 꺼내 후속 작업의 진입차수를 줄입니다.
4. 결과 길이가 n보다 작으면 사이클입니다.

JavaScript 풀이

function solution(n, dependencies) {
  const graph = Array.from({ length: n }, () => []);
  const indegree = Array(n).fill(0);
  for (const [before, after] of dependencies) {
    graph[before].push(after);
    indegree[after] += 1;
  }
  const queue = [];
  for (let node = 0; node < n; node += 1) {
    if (indegree[node] === 0) queue.push(node);
  }
  const order = [];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);
    for (const next of graph[node]) {
      indegree[next] -= 1;
      if (indegree[next] === 0) queue.push(next);
    }
  }
  return order.length === n ? order : [];
}

복잡도

• 시간복잡도: O(V + E)
• 공간복잡도: O(V + E)
• 핵심 패턴: 진입차수 0 정점을 큐로 처리하며 선행 간선 제거
• 경계 사례: 결과 정점 수가 n보다 작으면 사이클

연습 문제

1. 네트워크 그룹 수

연결 쌍을 합친 그룹 수를 반환하세요.

2. 첫 사이클 간선

처음 사이클이 생기는 간선 위치를 반환하세요.

3. 가장 이른 학기

선수 관계로 각 과목의 이른 학기를 반환하세요.

자주 하는 실수

• 진입차수를 반대 방향에 더하는 실수
• 0이 되는 순간 큐에 넣지 않는 실수
• 결과 길이로 사이클을 확인하지 않는 실수
• find에서 대표를 끝까지 따라가지 않는 실수

핵심 정리

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

확인 문제

참고 자료

• Princeton Algorithms 4e - Union-Find 
• Princeton Algorithms 4e - Graphs 
• MIT OpenCourseWare 6.006 Introduction to Algorithms