**Jeanie's Route

사이트: HackerRank
난이도: 미디움
분류: Graph Theory

문제

우편 배달부 Jeanie는 Byteland N개의 도시에 우편을 배달해야 한다. 각 도시는 반드시 다른 도시로 이어지는 경로가 존재할 때, Jeanie가 모든 우편을 배달할 수 있는 가장 작은 거리 값이 무엇인지 반환하라.

1. 나의 풀이

각 도시의 경로를 생성하고 bfs 알고리즘을 사용하여 경로들의 거리 값을 계산하였다. 거리 값을 다 구하고 난 다음 마지막에 가장 높은 비용인 거리 값을 뺀 나머지를 반환하려고 했는데, 잘 해결되지 않았다.

function getPairs(cities) {
    const pairs = [];
    
    for (let i = 1; i < cities.length; i++) {
        pairs.push([cities[i - 1], cities[i]]);
    }
    
    if (cities.length > 2) {
        pairs.push([cities[0], cities[cities.length - 1]]);
    }
    
    return pairs;
}

function getGraph(n, roads) {
    const graph = Array.from(
        new Array(n + 1),
        () => []
    );
    
    roads.forEach(([u, v, d]) => {
        graph[u].push([v, d]);
        graph[v].push([u, d]);
    });
    
    return graph;
}

function bfs(graph, start, end) {
    const visited = new Set([start]);
    const queue = [[start, 0]];
    let result = Infinity;

    while(queue.length) {
        const [current, distance] = queue.shift();
        
        for (const [next, d] of graph[current]) {
            if (!visited.has(next)) {
                if (next == end) {
                    result = Math.min(result, distance + d);
                } else {
                    visited.add(next);
                    queue.push([next, distance + d]);
                }
            }
        }
    }
    
    return result;
}

/*
 * Complete the jeanisRoute function below.
 */
function jeanisRoute(n, k, cities, roads) {
    /*
     * Write your code here.
     */
    const pairs = getPairs(cities);
    const graph = getGraph(n, roads);
    let total = 0, max = 0;
    
    pairs.forEach(([start, end]) => {
        const result = bfs(graph, start, end);
        max = Math.max(result, max);
        total += result;
    });
    
    return total - max;
}

2. 다른사람의 풀이

일단은 재귀형식의 dfs 풀이 방법이 있어서 자바스크립트 코드로 변환하여 가져왔다. 역시나 입력 값이 커서 Runtime error가 발생하긴 하지만, 그것만 제외하면 정상적으로 동작하는 코드이다.(stack이 아닌 재귀형식의 dfs가 더 유용한 상황이 많은 것 같다.)

추후 시간적 여유가 된다면, 해당 로직을 다시 분석해서 stack 형식의 dfs로 풀어봐야겠다.

function jeanisRoute(n, k, cities, roads) {
    /*
     * Write your code here.
     */
    const graph = Array.from(
        new Array(n + 1),
        () => ({})
    );
    const cs = new Set(cities);
    
  	// graph를 초기화한다.
    for (const [u, v, d] of roads) {
        graph[u][v] = d;
        graph[v][u] = d;
    }

    const visited = new Set();
    const ans = [0, 0];

    function dfs(node, dis = 0) {
        const minus = [0, 0];
        let isBelong = cs.has(node);
        
        visited.add(node);

        Object.entries(graph[node])
            .forEach(([next, val]) => {
                if (!visited.has(+next)) {
                    const d = dfs(+next, dis + val) - dis;
                    
                    if (d > 0) {
                        isBelong = true;
                        ans[0] += 2 * graph[node][next];
                        
                        if (d > minus[0]) {
                            minus[1] = Math.max(...minus);
                            minus[0] = d;
                        } else {
                            minus[1] = Math.max(minus[1], d);
                        }
                    }
                }
            });
        ans[1] = Math.max(ans[1], minus[0] + minus[1]);
        
        return isBelong ? dis + Math.max(...minus) : 0;
    }
    
    dfs(cities[0]);
    
    return ans[0] - ans[1];
}