[프로그래머스] 도넛과 막대그래프

도넛, 막대, 8자 그래프 문제 해결기

오늘 코딩테스트에서 만난 그래프 문제가 생각보다 까다로웠다. 처음에는 간단해 보였는데, 시간초과 때문에 몇 번이나 다시 짜야 했다.

문제 이해

문제는 도넛 모양, 막대 모양, 8자 모양 그래프들이 하나의 중심 정점에 연결되어 있을 때, 각 그래프의 개수를 세는 것이었다.

• 도넛: 정점 수 = 간선 수 (순환)
• 막대: 정점 수 = 간선 수 + 1 (선형)
• 8자: 정점 수 = 간선 수 - 1 (두 도넛이 만남)

첫 번째 시도 - 시간초과

처음에는 단순하게 접근했다. 각 그래프를 탐색할 때마다 전체 간선 배열을 순회하는 방식이었는데, 이게 문제였다.

// 이렇게 하면 O(E²)가 되어서 시간초과
for (const [from, to] of edges) {
  if (from === vertex && to !== centerVertex) {
    totalEdges++;
    dfs(to);
  }
}

간선이 100만 개면 최악의 경우 1조 번 연산이 필요했다. 당연히 시간초과.

두 번째 시도 - 인접 리스트 도입

그래서 인접 리스트를 미리 만들어서 O(1)로 접근하도록 바꿨다.

// 인접 리스트 구성
if (!adjacencyList.has(from)) {
  adjacencyList.set(from, []);
}
adjacencyList.get(from).push(to);

이제 각 정점의 인접한 정점들을 미리 저장해두고, 탐색할 때는 그 리스트만 확인하면 됐다.

세 번째 시도 - 더 극단적인 최적화

아직도 부족했다. 몇 가지 더 최적화할 부분이 있었다:

1. 불필요한 Set 제거: vertices Set을 만들 필요 없이 Map의 키만 사용
2. shift() 연산 제거: 배열의 shift()는 O(N)이라서 포인터 기반으로 바꿨다
3. 조건문 간소화: 그래프 타입 판별을 차이값 계산으로 단순화

// shift() 대신 포인터 사용
let queueIndex = 0;
while (queueIndex < queue.length) {
  const vertex = queue[queueIndex++];
  // ...
}

// 조건문 간소화
const diff = totalEdges - totalVertices;
if (diff === 0) donutCount++;
else if (diff === -1) barCount++;
else if (diff === 1) eightCount++;

최종 결과

이렇게 최적화하니 시간복잡도는 O(V + E)로 유지되면서도 상수 계수가 크게 줄어들었다. 100만 개 간선도 무리 없이 처리할 수 있게 됐다.

배운 점

1. 시간복잡도만으로는 부족하다: O(N)이어도 상수 계수가 크면 시간초과가 날 수 있다
2. JavaScript의 함정: shift(), unshift() 같은 연산은 생각보다 비싸다
3. 메모리도 최적화: 불필요한 자료구조는 만들지 말자
4. 극단적 최적화의 필요성: 코딩테스트에서는 극한까지 최적화해야 한다

앞으로는 처음부터 이런 최적화를 염두에 두고 코딩해야겠다. 특히 대용량 데이터가 나올 수 있는 문제에서는 더욱 그렇다.

최종 코드

function solution(edges) {
  const inDegree = new Map();
  const outDegree = new Map();
  const adjacencyList = new Map();

  for (const [from, to] of edges) {
    outDegree.set(from, (outDegree.get(from) || 0) + 1);
    inDegree.set(to, (inDegree.get(to) || 0) + 1);

    if (!adjacencyList.has(from)) {
      adjacencyList.set(from, []);
    }
    adjacencyList.get(from).push(to);
  }

  let centerVertex = -1;
  for (const [vertex, out] of outDegree) {
    const inCount = inDegree.get(vertex) || 0;
    if (out >= 2 && inCount === 0) {
      centerVertex = vertex;
      break;
    }
  }

  const centerOutEdges = adjacencyList.get(centerVertex) || [];
  let donutCount = 0,
    barCount = 0,
    eightCount = 0;

  for (const startVertex of centerOutEdges) {
    const visited = new Set();
    const queue = [startVertex];
    let queueIndex = 0;
    let totalEdges = 0,
      totalVertices = 0;

    while (queueIndex < queue.length) {
      const vertex = queue[queueIndex++];
      if (visited.has(vertex)) continue;

      visited.add(vertex);
      totalVertices++;

      const neighbors = adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        if (neighbor !== centerVertex) {
          totalEdges++;
          if (!visited.has(neighbor)) {
            queue.push(neighbor);
          }
        }
      }
    }

    const diff = totalEdges - totalVertices;
    if (diff === 0) donutCount++;
    else if (diff === -1) barCount++;
    else if (diff === 1) eightCount++;
  }

  return [centerVertex, donutCount, barCount, eightCount];
}