107. 이것이 코딩 테스트다 9장 : 미래 도시 Javascript

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 방문 판매원 A가 1번에서 시작해 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 구하라
• 주어진 자료는 무엇인가?
   - M = 경로를 나타낸 배열
   - X = 정수
   - K = 정수
• 조건은 무엇인가?
   - 만약 X번 회사에 도달할 수 없다면 -1을 출력한다

2. 계획

1. 1번에서 K번까지 가는 최단 경로를 구하라
2. K에서 X번까지 가는 최단 경로를 구하라
3. 이 둘을 더해서 리턴

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const solution = (route, K, X) => {
  let count = 0;

  // 1번에서 K번까지 가는 최단 경로를 구하라
  const arr = route.filter(it => it[0] === 1);

  let kRoute = [];
  if (arr.some((it) => it[1] === K)) {
    count++
  } else {
    for (i = 0; i < arr.length; i++) {
      kRoute.push(route.filter(it => it[0] === arr[i][1]))
    }
    count++
  }

  if (kRoute.length === 0) {
    return -1
  }

  const routeK = kRoute.reduce((acc, cur) => [...acc, ...cur]);
  if (routeK.some((it) => it[1] === K)) {
    count++
  }

  // K에서 X번까지 가는 최단 경로를 구하라
  let xRoute = [];
  if (route.some((it) => it[0] === K)) {
    xRoute.push(route.filter((it) => it[0] === K))
  } else {
    xRoute.push(route.filter((it) => it[1] === K))
  }

  const routeX = xRoute.reduce((acc, cur) => [...acc, ...cur]);
  if (routeX.some((it) => it[0] === X || it[1] === X)) {
    count++
  }
  return count
};

test('countMoney', () => {
  expect(solution([[1, 2], [1, 3], [1, 4], [2, 4], [3, 4], [3, 5], [4, 5]], 5, 4)).toEqual(3);
  expect(solution([[1, 3], [2, 4]], 3, 4)).toEqual(-1);
});

4. 반성

• 문제 해설에서 말한 것처럼 플로이드 워셜 알고리즘을 이용해서 해결할 수 있다.