[프로그래머스] 도넛과 막대 그래프

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

프로그래머스

문제를 접했을 때 가장 먼저 구해야 하는 것은 새로 생성된 노드를 찾는 것이라고 생각함

 

새로 생성된 노드의 특징은 나가는 간선이 2개 이상이고 들어오는 간선은 없다는 것임

 

따라서 graph를 만드는 과정에서 들어오는 간선의 수를 구해주고 새로 생성된 노드를 찾을 수 있음

 

생성된 노드 기준으로 탐색을 하며 각 그래프를 탐색하면 되는데 처음엔 각 그래프의 특징을 잡는 접근 방식을 사용했지만 문제에서 정의해 주듯 노드와 간선의 개수로 그래프를 구분함

 

테스트 케이스 중 하나의 케이스에서 시간초과가 발생했는데 이는 graph와 incomes를 선언할 대 Map 구조 사용이 원인이었음. 그래서 객체로 수정하여 해결

• 편의상 자주 사용했지만 정말 필요한 상황이 아니라면 사용하지 않는 것이 바람직함

각 그래프를 순회할 때 재귀 함수방식을 사용했었지만 내부 로직이 많이 어려워지므로 queue를 통해 순회하는 방식으로 수정함.

• 일반적인 탐색방식을 사용하면 루프가 발생하기 때문에 해당 노드에서 다음 노드로 넘어갈 때 간선의 개수를 계산하고 방문하지 않은 노드가 있을 때 queue에 추가하는 방식을 사용함

function solution(edges) {
    var answer = [];
    const graph = {};
    const incomes = {};
    let maxNode = 0;
    let addNode = 1;
    let dGraph = 0, sGraph = 0, eGraph = 0;
    
    edges.forEach(edge => {
        const [from, to] = edge;
        if(!graph[from]) graph[from] = [];
        graph[from].push(to);
        if(!graph[to]) graph[to] = [];
        
        incomes[to] = (incomes[to] || 0) + 1;
        incomes[from] = (incomes[from] || 0);
    })
    
    for(const cnt in incomes){
        if(incomes[cnt] == 0 && graph[cnt].length > 1){
            addNode = +cnt;
        }
    }
    
    const dfs = (sub) => {
        const seen = new Set([sub]);
        const queue = [sub];
        
        let edgeCnt = 0;
        
        while(queue.length > 0){
            const curr = queue.shift();
            const nexts = graph[curr];

            if(nexts){
                for(const next of nexts){
                    edgeCnt++;
                    if(!seen.has(next)){
                        seen.add(next);
                        queue.push(next);
                    }
                }
            }
        }
        
        if(seen.size == edgeCnt){
            dGraph++;
        }
        if(seen.size - 1 == edgeCnt){
            sGraph++;
        }
        if(seen.size + 1 == edgeCnt){
            eGraph++;
        }
    }
    
    for(const node of graph[addNode]){
        dfs(node);
    }
    
    answer = [addNode, dGraph, sGraph, eGraph];
    
    return answer;
}