[프로그래머스#JS] 여행 경로

문제

https://programmers.co.kr/learn/courses/30/lessons/43164

풀이

1. 처음부터 정렬하면 index 순으로 돌기 때문에 자동으로 알파벳 순으로 여행 경로가 설정됩니다.
2. 시작을 'ICN'으로 두고 DFS.
3. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 이 한마디 때문에 엄청 헤맸습니다. 최종 정답이 모든 도시를 방문할 수 있다는 얘기지, 아무렇게나 가도 모든 도시를 방문할 수 있다는 말이 아닙니다. 아래의 테스트 케이스로 DFS를 딱 한 번만 돌리면 모든 도시를 방문할 수 없습니다.

const tickets = [
  ['ICN', 'COO'],
  ['ICN', 'BOO'],
  ['COO', 'ICN'],
  ['BOO', 'DOO'],
];

4. path의 길이가 tickets 길이의 +1 일 때, 모든 도시를 방문할 수 있는 path고, 가능한 길을 answer 배열에 모두 넣습니다. 처음에 정렬을 했기 때문에 answer[0]이 정답이 됩니다.

코드

function solution(tickets) {
  tickets = tickets.sort();
  let isVisited = new Array(tickets.length).fill(false);
  let path = ['ICN'];
  let answer = [];

  function DFS(FROM) {
    if (path.length === tickets.length + 1) {
      answer.push([...path]);
      return;
    }

    tickets.forEach(([from, to], i) => {
      if (from === FROM && !isVisited[i]) {
        isVisited[i] = true;
        path.push(to);

        DFS(to);

        isVisited[i] = false;
        path.pop(to);
      }
    });
  }

  DFS('ICN');

  return answer[0];
}