도넛과 막대 그래프 문제 풀이 후기 🍩📊

이번 포스팅에서는 프로그래머스 도넛과 막대 그래프 문제를 해결했던 과정을 공유함.
문제의 핵심은 그래프의 연결 관계를 분석하여,

• 새로 생성된 노드: 들어오는 연결(comeInCnt)이 0이고 나가는 연결이 2개 이상인 노드
• 막대 그래프 (Pole): 자신으로 되돌아오지 않은 경우 (나가는 연결이 0인데 들어오는 연결이 있는 노드)
• 8자 그래프: 이미 방문한 노드를 2회 방문했을 때의 규칙 등
  을 이용해 도넛, 막대, 8자 그래프의 개수를 결정하는 문제였음.

---

문제 개요 📌

• 입력:
  • 에지(edge) 정보가 int[][] edges 형태로 주어짐. 각 에지는 [from, to]
• 출력:
  • [생성된 노드 번호, 도넛 개수, 막대 그래프(폴) 개수, 8자 그래프 개수]
• 예시:
  • 반례: [[2, 3], [4, 3], [1, 1], [2, 1]]
    • 정답은 [2, 1, 1, 0]이어야 함.

---

내 초기 시도 (실패한 접근) 😓

처음에는 DFS를 사용해 각 노드를 순회하며 방문 횟수를 기반으로 도넛, 막대, 8자 그래프를 판별하려고 함.
아래 코드는 내가 작성했던 초기 시도임:

import java.util.*;
import java.io.*;

class Solution {
    Set<Integer> nodes = new HashSet<>();
    Map<Integer, Boolean> visited = new HashMap<>();
    Map<Integer, Queue<Integer>> connInfo = new HashMap<>();
    int donutCnt, poleCnt, eightCnt;
    
    public int[] solution(int[][] edges) {
        setting(edges);
        // 디버그용 출력 생략...
        for (int cur : nodes) {
            if (!visited.get(cur)) {
                System.out.println();
                visited.put(cur, true);
                findConnNode(cur, 0);
                System.out.println(donutCnt + " " + poleCnt + " " + eightCnt);
            }
        }
        return new int[] {0};
    }
    
    private void findConnNode(int cur, int visitedCnt) {
        System.out.println(cur);
        Queue<Integer> nextNodes = connInfo.get(cur);
        if (nextNodes.isEmpty()) {
            if (visitedCnt == 2) eightCnt++;
            else if (visitedCnt == 1) donutCnt++;
            else poleCnt++;
        } else {
            int next = nextNodes.poll();
            if (visited.get(next)) visitedCnt++;
            visited.put(next, true);
            findConnNode(next, visitedCnt);
        }
    }
    
    private void setting(int[][] edges) {
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            nodes.add(from);
            nodes.add(to);
            visited.putIfAbsent(from, false);
            visited.putIfAbsent(to, false);
            connInfo.putIfAbsent(from, new ArrayDeque<>());
            connInfo.get(from).add(to);
            connInfo.putIfAbsent(to, new ArrayDeque<>());
        }
    }
}

문제점:

• DFS 기반 접근은 각 노드의 방문 횟수(visitedCnt) 를 기준으로 분류하려 했으나,
• 반례 [[2, 3], [4, 3], [1, 1], [2, 1]]와 같이 규칙이 복잡한 경우 예상한 결과를 얻지 못함.
• 즉, 그래프의 특성을 명확히 반영하지 못해 반례가 너무 많이 발생함.

---

내 정답 코드 (최적화된 내 접근) 💪

그래프의 특성을 활용하여 새로 생성된 노드는

• 들어오는 연결(comeInCnt)이 0이고,
• 나가는 연결(connInfo에서 확인) 수가 2개 이상이어야 함.

또한,

• 막대 그래프 (Pole): 자신으로 돌아오지 않았을 경우
• 8자 그래프: 이미 방문한 노드를 2회 방문했을 때로 분류함.

내 정답 코드는 아래와 같음:

import java.util.*;
import java.io.*;

class Solution {
    Set<Integer> nodes = new HashSet<>();
    Map<Integer, Integer> comeInCnt = new HashMap<>();
    Map<Integer, Boolean> visited = new HashMap<>();
    Map<Integer, Queue<Integer>> connInfo = new HashMap<>();
    int donutCnt, poleCnt, eightCnt;
    
    public int[] solution(int[][] edges) {
        setting(edges);
        int newNode = findNewNode();
        Queue<Integer> nextNodes = connInfo.get(newNode);
        while (!nextNodes.isEmpty()) {
            int next = nextNodes.poll();
            visited.put(next, true);
            int result = findConnNode(next);
            if (result == 0) poleCnt++;
            else if (result == 1) donutCnt++;
            else if (result == 2) eightCnt++;
        }
        return new int[] {newNode, donutCnt, poleCnt, eightCnt};
    }
    
    private int findNewNode() {
        for (int cur : nodes) {
            if (comeInCnt.get(cur) == 0 && connInfo.get(cur).size() > 1) return cur;
        }
        return -1;
    }
    
    private int findConnNode(int cur) {
        int result = 0;
        Queue<Integer> nextNodes = connInfo.get(cur);
        while (!nextNodes.isEmpty()) {
            int next = nextNodes.poll();
            if (visited.get(next)) result++;
            visited.put(next, true);
            result += findConnNode(next);
        }
        return result;
    }
    
    private void setting(int[][] edges) {
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            nodes.add(from);
            nodes.add(to);
            visited.putIfAbsent(from, false);
            visited.putIfAbsent(to, false);
            comeInCnt.putIfAbsent(from, 0);
            comeInCnt.put(to, comeInCnt.getOrDefault(to, 0) + 1);
            connInfo.putIfAbsent(from, new ArrayDeque<>());
            connInfo.get(from).add(to);
            connInfo.putIfAbsent(to, new ArrayDeque<>());
        }
    }
}

핵심 포인트:

• 각 노드의 들어오는 연결을 comeInCnt로 관리하여, 생성된 노드(들어오는 연결 0, 나가는 연결 ≥ 2)를 쉽게 찾음.
• DFS 대신, 연결 정보를 순회하며 방문 횟수를 카운트하여 8자, 도넛, 막대 그래프를 구분함.

---

참고할 만한 코드 (최적화된 배열 기반 접근) 📈

다른 사람의 최적화된 코드를 참고했음. 이 코드는 1,000,000 크기의 배열을 사용하여
각 노드의 ingoing과 outgoing 연결 수를 카운트하고,
단순 반복문을 통해 분류함.

class Solution {
    static int N = 1_000_000;

    public int[] solution(int[][] edges) {
        int[] ingoing = new int[N];
        int[] outgoing = new int[N];
        for (int[] edge : edges) {
            outgoing[edge[0]-1]++;
            ingoing[edge[1]-1]++;
        }
        int created = 0;
        int eight = 0;
        int stick = 0;
        for (int i = 0; i < N; i++) {
            if (outgoing[i] >= 2) {
                if (ingoing[i] == 0) {
                    created = i;
                } else {
                    eight++;
                }
            } else if (outgoing[i] == 0 && ingoing[i] > 0) {
                stick++;
            }
        }
        return new int[] {created+1, outgoing[created]-eight-stick, stick, eight};
    }
}

장점:

• 시간 효율성: 배열 기반으로 처리하므로 시간 복잡도가 낮음
• 코드 간결성: 단순 반복문 한 번으로 분류 가능

---