[bfs 알고리즘][javascript][node.js] 백준 2021번 최소 환승경로

2021번: 최소 환승 경로 (acmicpc.net)

2021번: 최소 환승 경로

기업 입사 코딩테스트에 비슷한 문제가 나왔는데, 시간 안에 못풀었다...

조금만 더 생각하면 풀 수 있었을만한 문제였기에 직접 풀어보았다.

 

해당 문제의 아이디어는 간단하다.

 

1. 모든 역을 허브로 본다.

2. 역=허브이며 역<->Set([레인(노선)]),  레인(노선)<->Set([역])을 저장한다.

3. bfs를 사용하는데 queue에 역을  push한다.

4. 해당 역에서 갈 수 있는 lane의 방문 여부를 기억하며, 해당 lane 내의 역들의 방문 정보를 해당 역으로부터의 거리로 저장한다.

5. 역과 lane의 방문 정보를 체크하면서 bfs를 지속한다.

 

개념 이해가 잘 안되면 아래 게시물을 보고오자

백준 최소 환승 경로 : 허브와 노드를 생각하자. (tistory.com)

백준 최소 환승 경로 : 허브와 노드를 생각하자.

위 게시물은 lane을 [100000+역인덱스]로 인덱싱하는 방식으로 해결하였다.

 

시간복잡도는 해당 문제는 안보는것 같지만, 100000 (허브의 갯수) +  1,000,000(간선의 총합)이 될 것이다

(모든 노선을 반복 순회하여도 간선 총합이 1000000이기 때문에 1000000이다. 엄마가 2명 있는데 아이가 총 10명 있으면 아이를 10명 보는것과 비슷함.)

 

추가사항 : 자바스크립트에서 set과 같은 해시 테이블 형태의 자료구조를 사용할 때, 버킷의 갯수를 동적으로 증가시키는 로직이 있다. 이 경우 재조정이 일어나므로 처음에 set의 크기를 설정해 두는게 도움이 된다. 면접 혹은 코딩테스트에 나올 수 있음...

/** @type  {number[][]} */
const input = require('fs')
  .readFileSync('/dev/stdin', 'utf8')
  .trim()
  .split('\n')
  .map((d) => d.split(' ').map((d) => +d));

function solution() {
  const [stationCnt, laneCnt] = input[0];
  const [startStation, endStation] = input[input.length - 1];

  /** @type {{ [lane:number] : Set<number>}} */
  const laneHubsSet = {};
  /** @type {{ [hub:number] : Set<number>}} */
  const hubLanesSet = {};
  range(1, laneCnt + 1).forEach((lane) => {
    laneHubsSet[lane] = new Set();
    input[lane].forEach((hubNumber) => {
      if (hubNumber === -1) return;
      hubLanesSet[hubNumber] = hubLanesSet[hubNumber] || new Set();
      laneHubsSet[lane].add(hubNumber);
      hubLanesSet[hubNumber].add(lane);
    });
  });
  return bfs(startStation, endStation, laneHubsSet, hubLanesSet);
}

console.log(solution());

/**
 *
 * @param {number} from
 * @param {number?} to
 * @returns {number[]} range
 */
function range(from, to) {
  const arr = [];
  arr.push;
  if (!to) {
    for (let i = 0; i < from; i++) {
      arr.push[i];
    }
    return arr;
  }

  for (let i = from; i < to; i++) {
    arr.push(i);
  }
  return arr;
}
/**
 *
 * @param {*} start
 * @param {*} end
 * @param {{ [lane:number] : Set<number>}} laneHubsSet
 * @param {{ [hub:number] : Set<number>}} hubLanesSet
 */
function bfs(start, end, laneHubsSet, hubLanesSet) {
  if (start === end) return 0;
  /** @type {{ [lane:number] : boolean}} */
  const laneVisitYn = {};
  /** @type {{ [hub:number] : number}} */
  const hubVisitDist = {};
  const q = [start];
  hubVisitDist[start] = 0;
  while (q.length) {
    const curHub = q.shift();
    const hubToLanes = [...hubLanesSet[curHub]];

    for (let lane of hubToLanes) {
      if (laneVisitYn[lane]) continue;
      laneVisitYn[lane] = true;
      if (laneHubsSet[lane].has(end)) {
        return hubVisitDist[curHub];
      }
      [...laneHubsSet[lane]].forEach((hub) => {
        if (hubVisitDist[hub] !== undefined) return;
        hubVisitDist[hub] = hubVisitDist[curHub] + 1;
        q.push(hub);
      });
    }
  }
  return -1;
}