[프로그래머스] 도넛과 막대그래프 (2024 KAKAO WINTER INTERNSHIP)

문제 설명을 제대로 읽고 풀이를 해야한다는 것을 느끼게 했던 문제였다.
처음에는 그래프 탐색을 통해서 문제를 해결하려고 했었는데 런타임 에러가 발생했다.
런타임 에러의 원인을 알 수는 없지만 아마도 메모리 문제였을 것이라고 추측한다.

그래서 질문하기를 통해서 다른 사람들의 풀이를 참고했고, 그래프의 특성을 잘 파악해서 문제를 해결할 수 있다는 것을 알게 됐다.

이 문제는 생성 정점과 도넛, 막대, 팔자 그래프의 수를 구하는 문제이다.

먼저, 가장 오랜 시간을 할애 했던 부분은 생성 정점이 무엇인지 알아내는 부분이었다. 문제 설명에서 그래프는 2개 이상이라고 조건을 설정해두었기 때문에 생성 정점의 진출 간선은 2개 이상이다. 그리고 어떤 그래프도 생성 정점으로 진출하지 않기 때문에 진입 간선이 0개다. 즉, 진출 간선이 2개 이상이면서 진입 간선이 0개인 정점이 생성 정점이다. 생성 정점이 진출한 간선의 수를 통해서 전체 그래프의 수를 알아낼 수 있다.

주어진 간선 정보를 통해서 어떤 정점이 몇 개의 진입 간선과 진출 간선을 갖는지를 정점별로 정리한다.
정리된 정점들을 탐색하면서 생성 정점을 찾고, 총 그래프 수를 확인한다.

그리고 가장 어려웠던 부분이 도넛/막대/팔자 그래프 모양을 구분하는 부분인데, 나는 이 부분을 그래프 탐색을 통해서 간선과 정점의 수를 카운트해서 모양을 확인하려고 했었다. 그런데 사실 이 문제에서 중요한 것은 각 그래프의 특성을 파악하는 것이었다. 모든 정점을 탐색하면서 어떤 정점이 하나의 진출 간선도 갖고 있지 않다면 그 것은 막대 그래프이다. 또, 어떤 정점이 2개 이상의 진입 간선과 진출 간선을 갖고 있다면 그 것은 팔자 그래프이다. 위의 조건을 통해서 모든 정점들을 확인한 후에 그래프의 수를 확인할 수 있다.

이 문제에서 설명한 size는 문제 풀이에서 전혀 사용되지 않았다는 점이 흥미로웠다.

function solution(edges) {
  let 생성정점 = 0;
  let 총그래프수 = 0;
  let 도넛 = 0;
  let 막대 = 0;
  let 팔자 = 0;

  const graph = {};
  edges.forEach(([from, to]) => {
    if (!graph[from]) {
      graph[from] = { fromCount: 0, toCount: 0 };
    }

    if (!graph[to]) {
      graph[to] = { fromCount: 0, toCount: 0 };
    }

    graph[from].fromCount++;
    graph[to].toCount++;
  });

  for (let key in graph) {
    const { fromCount, toCount } = graph[key];
    if (fromCount >= 2 && toCount === 0) {
      생성정점 = Number(key);
      총그래프수 = fromCount;
    }

    if (fromCount === 0) 막대++;
    if (fromCount >= 2 && toCount >= 2) 팔자++;
  }

  도넛 = 총그래프수 - 막대 - 팔자;

  return [생성정점, 도넛, 막대, 팔자];
}

출처
도넛과 막대 그래프: https://school.programmers.co.kr/learn/courses/30/lessons/258711