문제 링크

Bus Routes - LeetCode

문제 풀이

문제는 버스지만 지하철로 생각하고 풀었다.

routes 는 2차원 배열인데 1차원 index 는 호선이라 생각하고 각 배열의 원소는 역의 이름으로 생각하였다. map 을 통해 각 역이 어느 호선에 포함되는지 넣어주고 시작역의 호선을 q 에 넣음과 동시에 각 호선마다 몇 번 환승했는지 체크해주는 dist 도 초기 값을 넣어주었다.

BFS는 q에서 나온 원소는 호선이기때문에 반복문을 통해 그 호선의 역을 쭉 돌아서 target 역이라면 값을 return 한다. 그리고 각 역을 지나가면서 그 역이 어느 호선에 포함돼있는지 확인 후 만약 다른 호선에 포함된 역이라면 dist 값 비교를 통해 q에 넣을지 말지 결정한다.

나의 코드

var numBusesToDestination = function (routes, source, target) {
  if (source === target) return 0;
  const map = new Map();
  const dist = new Map();
  const q = [];
  for (let i = 0; i < routes.length; ++i)
    for (let j = 0; j < routes[i].length; ++j) {
      const tmp = map.get(routes[i][j]) || [];
      tmp.push(i);
      map.set(routes[i][j], tmp);
      if (routes[i][j] === source) {
        dist.set(i, 1);
        q.push(i);
      }
    }
  while (q.length) {
    const lane = q.shift();
    const val = dist.get(lane);
    for (let i = 0; i < routes[lane].length; ++i) {
      if (routes[lane][i] === target) return val;
      const otherLanes = map.get(routes[lane][i]);
      for (let j = 0; j < otherLanes.length; ++j) {
        const nextDist = dist.get(otherLanes[j]);
        if (nextDist === undefined || nextDist > val + 1) {
          q.push(otherLanes[j]);
          dist.set(otherLanes[j], val + 1);
        }
      }
    }
  }
  return -1;
};