*Minimum Penalty Path

sun202x·2022년 11월 28일

JavaScript algorithm

알고리즘

목록 보기

46/49

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

문제

N개의 정점과 M개의 간선이 포함된 그래프가 주어졌을 때, 각 간선 M[i]에는 패널티(비용)가 부여된다. 어떤 정점 A와 B를 지나가는 경로 중 가장 적은 비용을 반환하라.

패널티는 각 간선의 비용을 OR 비트 연산을 하여 계산한다.

1. 나의 풀이

bfs 알고리즘을 통해 A 노드에서 시작하여 B 노드까지 도달할 수 있는 모든 경로의 비용 값을 계산하여 가장 작은 값을 반환하도록 하였다.

어디서 문제가 생겼는지 모르겠지만, 테스트 케이스를 대부분 통과하지 못하였다.
(다른 사람들이 푼 코드도 봤는데, 내가 짠 것이랑 별반 다를게 없어 보였고 실제로 통과하는 코드를 보지 못했다. 해당문제는 추후 다시 정리하는 것으로 결정했다.)

function bfs(start, end, graph) {
    const queue = [[start, 0]];
    const visited = [];
    visited[start] = true;
    
    let result = Infinity;
    while (queue.length) {
        const [current, cost] = queue.shift();
        
        for(let i = 0; i < graph[current].length; i++) {
            const c = graph[current][i];
            
            if (c > 0 && !visited[i]) {
              	// B 노드일 경우 현재까지 계산된 cost 비용을 비교 후 가장 적은 비용을 저장한다.
              	// B 노드가 끝이므로 queue에 넣진 않는다.
                if (i == end) {
                    result = Math.min(result, cost | c);
                    
                } else {
                    queue.push([i, cost | c]);
                    visited[i] = true;
                }
            }
        }
    }
    
  	// B 노드에 도달할 수 없는 경우 result가 초기 값이므로 -1을 반환한다.
    return result === Infinity ? -1 : result;
}

function beautifulPath(n, edges, A, B) {
    // Write your code here
    const graph = Array.from(
        new Array(n + 1),
        () => new Array(n + 1)
    );

    edges.forEach(([u, v, c]) => {
        graph[u][v] = Math.min(c, (graph[u][v] || Infinity));
        graph[v][u] = Math.min(c, (graph[v][u] || Infinity));
    });

    return bfs(A, B, graph);
}