[Lv2] 배달

https://programmers.co.kr/learn/courses/30/lessons/12978?language=javascript 

코딩테스트 연습 - 배달

---

양방향이고, 한 도시에 도달할 수 있는 경로가 여러개인 경우,

 

'방문했던 도시는 다시 방문하지 않는다'의 조건문을 만드는게 아니라,

 

'특정 도시에 두 번 방문할 때, 이전에 방문한 경우보다 비용이 더 많이 드는 경우 방문하지 않는다'의 조건문이 필요함.

 

아래 그림 참고

 

 

 

 

1. TEST CASE 32번 통과하지 못한 코드

// ***condition***
// 1<=N<=50
// 1<=road.len<=2,000
// road = [start, end, time]
// 1<=K<=500,000


function solution(N, road, K) {
    var map = new Map();
    var visited = new Set().add(1);

    for(let [start, end, time] of road) {
        if(!map.has(start)) {
            map.set(start,[[end, time]]);
        } else if(map.has(start)) {
            let info = map.get(start);
            info.push([end, time]);
            map.set(start, info);
        }
        if(!map.has(end)) {
            map.set(end,[[start, time]]);
        } else if(map.has(end)) {
            let info = map.get(end);
            info.push([start, time]);
            map.set(end, info);
        }
    }
    
    let connectedCity = map.get(1);
    for(let [nextCity, time] of connectedCity) {
        if(time <= K) {
            visited.add(nextCity);
            search(nextCity, time, [1, nextCity]);
        }
    }
    
    function search(city, accTime, visiting) {
        if([...visited].length === N) return;
        
        let connectedCity = map.get(city);
        if(connectedCity) {
            for(let [nextCity, time] of connectedCity) {
                if(visiting.includes(nextCity) || accTime + time > K) continue;
                else {
                    visited.add(nextCity);
                    search(nextCity, accTime + time, [...visiting, nextCity]);
                }
            }
        }
    }
    
    return [...visited].length;
}

 

2. TEST CASE 32번 통과한 코드

function solution(N, road, K) {
    var map = new Map();
    var visited = new Set().add(1);
    var visitedTime = new Map().set(1, 0);


    // 연결 정보를 모두 객체에 저장
    // 한 도로의 정보가 여러 번 중복해서 주어지지 않으므로, End도 저장해주어야 함.
    for(let [start, end, time] of road) { 
        if(!map.has(start)) {
            map.set(start,[[end, time]]);
        } else if(map.has(start)) {
            let info = map.get(start);
            info.push([end, time]);
            map.set(start, info);
        }
        if(!map.has(end)) {
            map.set(end,[[start, time]]);
        } else if(map.has(end)) {
            let info = map.get(end);
            info.push([start, time]);
            map.set(end, info);
        }
    }
    
    // 출발 지점 도시1을 기준으로 주변 도시 탐색
    let connectedCity = map.get(1);
    for(let [nextCity, time] of connectedCity) {
        if(time <= K) {
            visited.add(nextCity);
            visitedTime.set(nextCity, time);
            search(nextCity, time, [1, nextCity]);
        }
    }
    
    function search(city, accTime, visiting) {
        if([...visited].length === N) return; // 모든 도시의 탐색이 끝난 경우
        if(visitedTime.get(city) < accTime) return; // 해당 도시를 더 짧은 시간에 방문한 경우
        
        let connectedCity = map.get(city);

        if(connectedCity) { // 본 문제에선 문제가 안되지만, 다른곳에서는 문제가 될 수 있음. 항상 체크하자!
            for(let [nextCity, time] of connectedCity) {
                if(visiting.includes(nextCity) || accTime + time > K) continue;
                else {
                    visited.add(nextCity);
                    if(!visitedTime.has(nextCity) || visitedTime.get(nextCity) > accTime + time) 
                        visitedTime.set(nextCity, accTime + time);
                    search(nextCity, accTime + time, [...visiting, nextCity]);
                }
            }
        }
    }
    
    return [...visited].length;
}

3. 다른 사람 풀이 Dijkstra algorithm 

https://juyoungpark718.github.io/posts/60

[프로그래머스] 레벨3 (level3) 배달

위 사이트를 참고하여 코드 변수명을 아래와 같이 수정함.

function solution(N, road, K) {
    var answer = 0;
    var minTime = new Array(N+1).fill(Infinity);
    var adj = new Array(N+1).fill(0).map(val => {return new Array()});

    for(let info of road) {
        let [start, end, time] = info;

        adj[start].push({ to : end , weight : time });
        adj[end].push({ to : start, weight : time });
    }

    let q = [{to : 1, weight : 0}];
    minTime[1] = 0;
    
    
    while(q.length) {
        let visited = q.pop();
        
        adj[visited.to].forEach(info => {
            if(minTime[info.to] > minTime[visited.to] + info.weight) {
                minTime[info.to] = minTime[visited.to] + info.weight;
                q.push(info);
            }
        });
    }

    minTime.forEach(val => {
        if(val <= K) answer++;
    })
    
    return answer;
}