[JS] 부대복귀

각 그래프의 간선의 길이가 1이므로 처음에는 단순히 bfs로 구하면 되는거 아니야? 라는 생각을 하게 되었다.

 

function solution(n, roads, sources, destination) {
  const graph = [...Array(n + 1)].map((_) => []);
  for (const [a, b] of roads) {
    graph[a].push(b);
    graph[b].push(a);
  }

  const getDist = (start, end) => {
    const visited = Array(n + 1).fill(false);

    const que = [[start, 0]];
    let idx = 0;
    while (que[idx]) {
      const [node, dist] = que[idx++];
      visited[node] = true;
      if (node === end) return dist;
      for (const nextNode of graph[node]) {
        if (!visited[nextNode]) que.push([nextNode, dist + 1]);
      }
    }
    return -1;
  };

  return sources.map((v) => getDist(v, destination));
}

 

 

어쩌면 당연한 것일 수 있지만 모든 케이스들에 대해서 다 bfs를 수행했기에 시간초과가 발생하였다.

 

 

어차피 각 지역에서 가는 목적지가 한 곳으로 고정되어 있으니, 역으로 목적지에서 각지역까지 가는 거리에 대해서 구해서 저장해둔다면 한번의 bfs만을 통해서 거리를 구하는 것이 가능하다.

 

 

따라서 dp를 하나 만들고 각 node에서 목적지까지 가는 거리를 저장해두는 방식으로 문제를 해결하였다.

 

 

 

 

function solution(n, roads, sources, destination) {
  const graph = [...Array(n + 1)].map((_) => []);
  for (const [a, b] of roads) {
    graph[a].push(b);
    graph[b].push(a);
  }

  const getDist = (end) => {
    const dp = Array(n + 1).fill(Infinity);
    dp[end] = 0;
    const que = [end];
    let idx = 0;
    while (que[idx]) {
      const node = que[idx++];

      for (const nextNode of graph[node]) {
        if (dp[nextNode] > dp[node] + 1) {
          dp[nextNode] = dp[node] + 1;
          que.push(nextNode);
        }
      }
    }
    return dp;
  };
  const dp = getDist(destination);
  return sources.map((v) => (dp[v] === Infinity ? -1 : dp[v]));
}