프로그래머스 / 도넛과 막대 그래프

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

프로그래머스

작성한 코드

[설명]
1. 추가된 edge는 나가는 path가 2개 이상이고, 들어오는 path(incoming)이 0개이다. -> 이를 이용해 추가된 edge 찾기
2. 추가된 edge를 기준으로 각 그래프가 어떤 그래피인지 판별한다. (DFS 이용)

public int[] solution(int[][] edges) {
        // Brute Force
        Map<Integer, List<Integer>> map = new HashMap<>();
        Set<Integer> incoming = new HashSet<>();
        
        int maxEdge = 0;
        // 먼저 정점에 연결된 정점들 정리
        for(int[] e: edges){
            List<Integer> list = map.getOrDefault(e[0], new ArrayList<Integer>());
            list.add(e[1]);
            map.put(e[0], list);
            incoming.add(e[1]);
            maxEdge = Math.max(maxEdge, Math.max(e[0], e[1]));
        }
        
        //System.out.println("map: " + map + ", incoming: " + incoming + ", maxEdge: " + maxEdge);
        int added = 0;
        
        for(int i = 1; i < maxEdge+1; i++){
            if(incoming.contains(i) || !map.contains(i)) continue;
            int pathNum = map.get(i).size();
            if(pathNum < 2)  continue;
            added = i;
        }
        
        // 도넛, 스틱, infinite 모양 갯수
        int[] graphs = new int[3];
        
        for(int c: map.get(added)){
            graphs[whatGraph(map,c)]++;
        }
        
        int[] answer = {added, graphs[1],graphs[2],graphs[0]};

        return answer;
    }
    
    public int whatGraph(Map<Integer, List<Integer>> map, int start){
        // 도넛인지 막대인지 8자인지 판별
        int edgeNum=0, pathNum = 0;
        Stack<Integer> stack = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        
        stack.push(start);
        
        while(!stack.isEmpty()){
            int curr = stack.pop();
            visited.add(curr);
            edgeNum++;;
            List<Integer> children = map.get(curr);
            if(children == null)    continue;
            
            for(int child: children){
                pathNum++;
                if(!visited.contains(child)){
                    stack.push(child);
                }
            }
        }
        
        return (edgeNum-pathNum)+1;
    }

 

다른 사람의 솔루션 참고

[설명]

- 추가된 edge는 (outgoing >= 2 && incoming == 0)
- 아무것도 나가지 않고 edge가 추가된 edge와 다른 경우 (outgoing == 0 && i != answer\[0]), 막대 그래프의 last edge
- 8자 그래프에는 가운데에 허리부분을 담당하는 edge가 하나만 존재 (outgoing >= 2 && incoming >= 2)인 edge

import java.util.*;

class Solution {
    final int MAX = 1000001;
    
    public int[] solution(int[][] edges) {
        int[] answer = new int[4];
        int[] outgoing = new int[MAX];
        int[] incoming = new int[MAX];
        int maxEdge = 0;
        
        for(int[] e: edges){
            outgoing[e[0]]++;
            incoming[e[1]]++;
            
            maxEdge = Math.max(maxEdge, Math.max(e[0],e[1]));
        }
        
        for(int i = 1; i <= maxEdge; i++){
            if(outgoing[i] == 0 && incoming[i] == 0)    continue;
            if(outgoing[i] >= 2 && incoming[i] == 0)
                answer[0] = i;
        }
        
        int total = outgoing[answer[0]];
        // 35번 테케에 의해 노드가 꼭 increasing하지 않을 수 있음
        
        for(int i = 1; i <= maxEdge; i++){
            if(outgoing[i] == 0 && incoming[i] == 0)    continue;
            
            if(outgoing[i] == 0 && i != answer[0]) // 막대 그래프 last edge
                answer[2]++;
            
            else if(outgoing[i] >= 2 && incoming[i] >= 2)   // 8자 그래프의 가운데 부분
                answer[3]++;
        }
        
        answer[1] = total - (answer[2]+answer[3]);
     
        return answer;
    }
}