작성일 : January 5, 2022

문제 : https://programmers.co.kr/learn/courses/30/lessons/12978

해설 : https://eunchanee.tistory.com/604

나의 풀이

DFS로 풀 수 있는줄 알았는데,, 복병이 있었다

마을과 마을 사이에 길이 2가지가 있으면 visited를 사용할 수 없다..

⇒ 문제를 제대로 읽어보지 않은 것이 패착 요인 🥲

// 마을의 개수 N
// K는 음식 배달이 가능한 시간

function solution(N, road, K) {
    var answer = 0;
    
    const 마을들 = Array.from({length:N}, (_,i) => i+1);
    const graph = new Map();
    
    function addNode(마을) {
        graph.set(마을, []);
    }
    
    function addEdge(origin, destination, weight) {
        graph.get(origin).push([destination, weight]);
        graph.get(destination).push([origin, weight]);
    }
    
    마을들.forEach(addNode);
    road.forEach(route => addEdge(...route))
    
    //console.log(graph.get(3));
    
    const dfs = (start, time, visited = new Set()) => {
        visited.add(start);
        
        const destinations = graph.get(start);
        
        destinations.forEach(destination => {
            if(destination[1] <= time && !visited.has(destination[0])) {
                //console.log(Array.from(visited));
                dfs(destination[0], time-destination[1], visited);
            }
        });
        
        console.log(Array.from(visited));
        
        answer = Math.max(answer, visited.size);
    }
    dfs(1, K);
    

    return answer;
}

풀이 해설

DFS가 아니라 BFS + 다익스트라로 문제 해결

function solution(N, road, K) {
    var answer = 0;
    
    const nodes = Array.from({length: N}, (_,i) => i+1);
    const graph = new Map();
    
    nodes.forEach(num => graph.set(num, []));
    
    road.forEach(arr => {
        const [start, end, weight] = arr;
        
        graph.get(start).push([end,weight]);
        graph.get(end).push([start,weight]);
    })
    
    const dist = Array.from({length: N+1}, () => Infinity);
    dist[1] = 0;
    const queue = [1];
    
    while(queue.length) {
        const start = queue.shift();
        
        graph.get(start).forEach(nextNode => {
            const [destination, weight] = nextNode;
            
            if(dist[destination] > dist[start] + weight) {
                dist[destination] = dist[start] + weight;
                
                queue.push(destination);
            }   
        })
    }

    return dist.filter(n => n <= K).length;
}

후기