프로그래머스 LEVEL 3(부대복귀)

사용 언어 : javascript
해결 날짜 : 2023-05-04
해결 방법 :
- dp와 bfs를 통해 문제 해결
  - destination인 곳은 0으로, 나머지는 Infinity로 dp 초기화
  - roads를 돌며 양방향 map 연결
  - destination을 첫번째로 하여 bfs 수행
    - 이 때 이전 dp값 + 1과 다음 dp값을 비교하여 다음 dp값이 클 경우에만 dp 업데이트 및 q에 push
회고 :
- 처음에 visited까지 활용하여 문제를 해결했으나 불필요하다고 생각되어 제거했다.
- 다른 사람들의 풀이를 보니 map까지 사용하지 않아도 되는 듯 하다.

코드

function solution(n, roads, sources, destination) {
  const dp = Array.from({ length: n + 1 }, (_, i) => (i === destination ? 0 : Infinity));
  const map = new Map();

  roads.forEach(([from, to]) => {
    map.has(from) ? map.set(from, [...map.get(from), to]) : map.set(from, [to]);
    map.has(to) ? map.set(to, [...map.get(to), from]) : map.set(to, [from]);
  });

  const q = [destination];

  while (q.length) {
    const from = q.shift();

    map.get(from).forEach((to) => {
      if (dp[from] + 1 < dp[to]) {
        dp[to] = dp[from] + 1;
        q.push(to);
      }
    });
  }

  return sources.map((source) => (dp[source] === Infinity ? -1 : dp[source]));
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges