문제 링크

프로그래머스 문제

풀이

노드를 순회하며, Tree 구조의 가장 마지막 위치인
leaf 의 개수를 찾는 문제이다.

DFS가 아닌 BFS로 푸는것이 합당해 보이는 문제이다.

function solution(n, edge) {
    var answer = 0;
    
    const graph = new Array(n+1).fill(0).map(v => new Array(n+1).fill(0))
    const visited = new Array(n+1).fill(false)
    for(let i=0; i< edge.length; i++){
        const [startNode , endNode] = edge[i]
        
        graph[startNode][endNode]=1
        graph[endNode][startNode]=1
    }
    
    const queue = [[1,1]] // curNode, curCount
    const LeafCount = new Array(n+1).fill(0)
     
    while(queue.length>0){
        const [curNode , curCount] = queue.shift()
        
        // 종료 조건
        // 방문했던 경우 종료
        if(visited[curNode]){
            continue;
        }else{
            visited[curNode]= true;
            LeafCount[curCount]++;
           
        }
        // 다음 조건
        for(let i=1; i <=n; i++){
            if(graph[curNode][i] >0 && !visited[i]){
             queue.push([i,curCount+1])   
            }
        }
    }
    
    for(let i=1; i<LeafCount.length; i++){
        if(LeafCount[i] > 0){
            continue;
        }
        else{
            
            return LeafCount[i-1]
        }
    }
    
}

하지만 다음과 같이 코드를 작성했을때ㅡ,

다음과 같은 문제가 발생하게 되었는데, 아마도 bfs 내부의 for문의 반복이 굉장히 커서 발생하는 문제라고 예상하게 되었다.
그에 따라 새로운 방식으로 구현하게 되었다.

for문에서는 해당 node와 연결된 node만은 순회할 수 있도록 변경하였다.

코드

function solution(n, edge) {
    var answer = 0;
    edge.map(v => v.sort((a,b) => a-b))
    
    const graph = new Array(n+1).fill(0).map(() => new Array())
    const visited = new Array(n+1).fill(false)
    
    for(let i=0; i< edge.length; i++){
        const [startNode , endNode] = edge[i]
        
        graph[startNode].push(endNode)
        graph[endNode].push(startNode)
        
    }
    
    const queue = [[1,1]] // curNode, curCount
    const LeafCount = new Array(n+1).fill(0)
     
    while(queue.length>0){
        const [curNode , curCount] = queue.shift()
        
        // 종료 조건
        // 방문했던 경우 종료
        if(visited[curNode]){
            continue;
        }else{
            visited[curNode]= true;
            LeafCount[curCount]++;
           
        }
        // 다음 조건
        for(let i=0; i <=graph[curNode].length; i++){
            if(graph[curNode][i] >0 && !visited[graph[curNode][i]]){
             queue.push([graph[curNode][i],curCount+1])   
            }
        }
    }

    for(let i=1; i<LeafCount.length; i++){
        if(LeafCount[i] > 0){
            continue;
        }
        else{
            
            return LeafCount[i-1]
        }
    }
    
}