[프로그래머스 level2] 도넛과 막대 그래프 자바 DFS (Map, Set)

https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

문제

각 정점별로 번호가 주어져 있고, 도형은 도넛과 막대, 8자 3가지가 존재한다.

주어진 정점 목록 edges를 참조하여

최초 출발 정점과 각 도형의 갯수를 구하여라.

참고사항

edges : 정점들 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
도넛 : edge == node
막대 :  edge == node -1
8자 : else

접근

edges를 정리하고 생성된 정점을 찾는 부분부터 막힘

피드백

1. inDegree / outDegree 계산 : edges에서 node 의 in out 분리 및 카운트.
2. 생성된 정점 찾기
3. 생성된 정점의 각 자식 정점 → DFS/BFS로 구조물 분리 - visited[]로 이미 탐색한 정점 건너뛰기
4. 구조물 정점/간선 수 체크 → 도넛/막대/8자 판단
5. 최종 [생성된 정점, 도넛 수, 막대 수, 8자 수] 반환

public int[] solution(int[][] edges) {
        Map<Integer, Integer> outs = new HashMap<>();
        Map<Integer, Integer> ins = new HashMap<>();
        Set<Integer> nodes = new HashSet<>();

        //1. edge 정리
        for(int[] edge : edges){
            int start = edge[0];
            int end = edge[1];

            outs.put(start, outs.getOrDefault(start, 0) + 1);
            ins.put(end, ins.getOrDefault(end, 0) + 1);
            nodes.add(start);
            nodes.add(end);
        }

        //2.edges에서 생성된 정점 찾기. 진입이 0이면서 진출 2개 이상인 것 찾기.
        int createdNode = -1;
        for(int node : nodes){
            if(outs.getOrDefault(node, 0) >= 2 && ins.getOrDefault(node, 0) == 0){
                createdNode = node;
                break;
            }
        }

        //3. 생성된 정점에서 시작된 간선들 수집?
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for(int[]edge : edges){
            graph.computeIfAbsent(edge[0], k-> new ArrayList<>()).add(edge[1]);
        }

        //4. 탐색
        int donut = 0, stick = 0, eight = 0;
        Set<Integer> visited = new HashSet<>();
        List<Integer> startNodes =graph.get(createdNode);
        if(startNodes != null){
            for(int next : startNodes){
                if(!visited.contains(next)){
                    int[] count = new int[]{0,0}; //nodes, edges
                    dfs(next, graph, visited, count);

                    int v = count[0], e = count[1];

                    if( e == v ) donut ++;
                    else if( e == v - 1) stick ++;
                    else eight ++;
                }
            }
        }


        return new int[]{createdNode, donut, stick, eight};
    }

    private void dfs(int node, Map<Integer,List<Integer>> graph, Set<Integer> visited, int[] count){
        visited.add(node);
        count[0] ++;
        if(graph.containsKey(node)){
            for(int next : graph.get(node)){
                count[1] ++;
                //미방문 체크
                if(!visited.contains(next)){
                    dfs(next,graph, visited, count);
                }
            }
        }
    }