Breadth First Search: Shortest Reach

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

문제

각 간선의 가중치가 6인 무방향 그래프가 있고 첫 시작점이 주어졌을 때, 각 노드 간의 최단 거리의 가중치를 계산하여 반환하라. 연결되지 않았을 때는 -1을 반환하도록 한다.

1. 나의 풀이

bfs 알고리즘만 잘 알고 있으면 쉽게 풀 수 있는 문제이다. 입력 값의 수가 적어서 queue를 따로 구현하지 않고 작성했다.

function bfs(n, m, edges, s) {
    // Write your code here
    const graph = Array.from(new Array(n + 1), () => []);

    edges.forEach(([u, v]) => {
        graph[u].push(v);
        graph[v].push(u);
    });
    
    const visited = new Array(n + 1).fill(0);
    const queue = [[s, Infinity]];
    
    visited[s] = Infinity;
    
    while(queue.length) {
        const [current, distance] = queue.shift();
        
        for (const next of graph[current]) {
            if (!visited[next]) {
                const _distance = distance === Infinity ? 1 : distance + 1;
                visited[next] = _distance;
                queue.push([next, _distance]);
            }
        }
    }
    
    return visited.reduce((ret, distance, i) => {
        if (i != 0 && i != s) {
            ret.push(distance ? distance * 6 : -1);
        }
        return ret;
    }, []);
}

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.