[프로그래머스] 도넛과 막대 그래프 풀이 및 코드 분석

문제 링크

---

1. 문제 분석

📌 문제 개요

• 주어진 단방향 그래프에서 다음 요소를 찾아야 한다:
  1. 생성된 정점 (모든 그래프의 진입점)
  2. 도넛 모양 그래프 개수 (순환)
  3. 막대 모양 그래프 개수 (끝점이 하나 있는 트리 구조)
  4. 8자 모양 그래프 개수 (두 개의 도넛이 연결된 구조)

---

2. 해결 방법

🔹 그래프 구성 및 특성

• edges를 이용하여 각 노드의 진입 차수 (in-degree)와 진출 차수 (out-degree)를 계산
• 생성된 정점 찾기:
  • out-degree >= 2이고 in-degree == 0인 노드 (다른 노드에서 진입하지 않고, 여러 노드로 나가는 노드)

🔑 그래프 분류

1. 도넛 모양 그래프: 모든 노드의 in-degree == 1 및 out-degree == 1 (즉, 사이클)
2. 막대 모양 그래프: in-degree == 0인 루트가 존재하는 트리 형태 (out-degree == 1)
3. 8자 모양 그래프: in-degree == 2 & out-degree == 2 (두 개의 도넛이 연결된 그래프)

---

3. 코드 구현 (Java)

import java.util.*;

class Solution {

    private Map<Integer, List<Integer>> map;

    private int[] visited;

    private int[][] e;    

    public int[] solution(int[][] edges) {
        int[] answer = new int[4];

        map = new HashMap<>();
        int maxNode = 0; 

        for (int[] arr : edges) {

            map.putIfAbsent(arr[0], new ArrayList<>());
            map.putIfAbsent(arr[1], new ArrayList<>());

            map.get(arr[0]).add(arr[1]);

            maxNode = Math.max(maxNode, Math.max(arr[0], arr[1]));
        }

        int last = maxNode + 1;
        e = new int[last][2];
        visited = new int[last];

        for (int i = 1; i < last; i++) {
            if (!map.containsKey(i)) continue;
            for (int a : map.get(i)) {
                e[i][0]++;
                e[a][1]++;
            }
        }

        // 생성한 정점의 번호
        for (int i = 1; i < last; i++) {
            if (e[i][0] >= 2 && e[i][1] == 0) {
                answer[0] = i;
                break;
            }
        }


        for (int next : map.get(answer[0])) {
            e[next][1]--;
        }

        // 8자 모양 그래프의 수
        for (int i = 1; i < last; i++) {
            if (i == answer[0] || visited[i] == 1) continue;

            if (e[i][0] == 2 && e[i][1] == 2) {
                visited[i] = 1;
                answer[3]++;
            }
        }

        // 막대 모양 그래프의 수
        for (int i = 1; i < last; i++) {
            if (i == answer[0] || visited[i] == 1) continue;
            if (!map.containsKey(i)) continue;

            if (e[i][1] == 0) {
                visited[i] = 1;
                answer[2]++;
            }
        }

        // 도넛 모양 그래프 수
        answer[1] = map.get(answer[0]).size() - answer[2] - answer[3];

        return answer;
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. 그래프 생성 및 in-degree, out-degree 계산 (O(N))
2. 생성된 정점 찾기 (O(N))
3. 그래프 유형 분류
   • O(N) 반복하며 도넛, 막대, 8자 그래프 개수 판별
   • 생성된 정점의 연결 노드 개수에서 막대 및 8자 그래프 개수를 빼서 도넛 개수 추론

---

5. 시간 복잡도 분석

• O(N)
  • N은 최대 1,000,000이므로 O(N) 알고리즘으로 해결 가능

---

6. 개선할 점 및 대체 방법

• DFS/BFS 탐색으로 그래프 유형을 판별하는 방식도 가능
• 하지만 현재 방식이 메모리 효율적이고 실행 속도가 빠름