프로그래머스 - 배달

07.06에 푼 문제입니다🌷

DFS 로 풀기

function solution(N, road, K) {
    if(N===1) return 1
    const result =new Set()
    const visited = new Array(N+1).fill(false)
  
    
    function dfs(num,weight){
        const route = road.filter(el=>el[0]===num||el[1]===num)
        visited[num]=true
        
        for(let el of route){
            if(weight+el[2]>K) continue
            
            if(!visited[el[0]]){
                dfs(el[0],weight+el[2])
            }
            else if(!visited[el[1]]){
                dfs(el[1],weight+el[2])
            }
        }result.add(num)
        visited[num]=false
    }

    dfs(1,0)
    return result.size;
}

처음에는 dfs로 접근해서 문제를 풀었다.
각 노드까지 접근하는 weight를 다 구했다.

32번에서 시간초과로 실패했다.
🤔🤔🤔🤔

다익스트라로 다시 풀기

function solution(N, road, K) {
    var answer = 0;
    road.sort((a,b)=>a[2]-b[2])
    let visited = new Array(N+1).fill(false)
    let distance = new Array(N+1).fill(Infinity)
    let pq=[]
    pq.push(1)
    visited[1]=true
    distance[1]=0
    
    for(let i=0;i<N;i++){
        let start=1
        let distancesort=distance.slice().sort((a,b)=>a-b)
        for(let dis of distancesort){
            if(!visited[distance.indexOf(dis)]){
                start=distance.indexOf(dis)
                break
            }
        }
        visited[start]=true
        let filterroad=road.filter(x=>x[0]===start||start===x[1])
        filterroad.map(el=>{
            let dist=el[0]
            if(start===dist) dist=el[1]
            
            if(distance[start]+el[2]<distance[dist])
                distance[dist]=distance[start]+el[2]
        })
        
    }
    
    return distance.filter(x=>x<=K).length;
}

🤔,,,,,

ㅠㅠ
결국 다른 분의 풀이를 보았다!