[Programmers] (Summer/Winter Coding(~2018)) Lv 2. 배달

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

프로그래머스

 

DFS(재귀)로 풀었지만, 32번 테스트가 시간 초과 실패.

function solution(N, road, K) {
    const graph = road.reduce((obj, [p1, p2, t]) => {
        (obj[p1] = obj[p1] || {}), (obj[p2] = obj[p2] || {});
        obj[p1][p2] = obj[p2][p1] = Math.min(obj[p1][p2] ? obj[p1][p2] : Infinity, t);
        return obj;
    }, {});

    return (dfs = (dest, distance, result, visited) => {
        (visited[dest] = true), result.add(dest);

        for (const key in graph[dest]) {
            if (visited[key] || distance + graph[dest][key] > K) continue;

            dfs(key, distance + graph[dest][key], result, visited);
            visited[key] = false;
        }

        return result;
    })("1", 0, new Set(), {}).size;
}

인접 리스트와 DFS(반복문)를 활용하여 다시 풀이.

function solution(N, road, K) {
    const graph = road.reduce((obj, [p1, p2, t]) => { 
        (obj[p1] = obj[p1] || {}), (obj[p2] = obj[p2] || {});
        obj[p1][p2] = obj[p2][p1] = Math.min(obj[p1][p2] ? obj[p1][p2] : Infinity, t);
        return obj;
    }, {}); // 무방향 그래프

    const stack = [{ dest: 1, cost: 0 }], // 첫 노드로 가는 정보를 삽입
        distance = new Array(N + 1).fill(Infinity); // distance는 각 노드의 최단 경로를 저장

    while (stack.length) { // dfs
        const { dest: cur, cost: cost } = stack.pop();

        if (distance[cur] > cost) distance[cur] = cost; // 최단 경로로 갱신

        for (const dest in graph[cur]) {
            if (distance[dest] < cost + graph[cur][dest]) continue; // dest 좌표의 경로 값보다, 현재 좌표에서 dest 좌표로 가는 경로가 크면 굳이 방문을 안함.
            stack.push({ dest: dest, cost: cost + graph[cur][dest] });
        }
    }
    return distance.filter((e) => e !== Infinity && e <= K).length; // K보다 낮은 최단 경로의 갯수만 추출
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/12978.%E2%80%85%EB%B0%B0%EB%8B%AC

GitHub - developeSHG/Algorithm-Baekjoon_Programmers: 백준 and 프로그래머스 소스코드