[Javascript/자바스크립트] (프로그래머스) 여행경로

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

코드

function solution(tickets) {
  let answer = [];
  const graph = new Map();
  for (let i = 0; i < tickets.length; i++) {
    const [s, e] = tickets[i];
    if (!graph.has(s)) {
      graph.set(s, []);
    }
    graph.get(s).push([i, e]);
  }

  for (const [k, v] of graph.entries()) {
    v.sort((a, b) => a[1].localeCompare(b[1]));
  }

  const visited = new Array(tickets.length).fill(false);
  const dfs = (now, path) => {
    if (path.length === tickets.length + 1) {
      answer = [...path];
      return;
    }
    if (answer.length > 0 || !graph.has(now)) return;

    for (const [idx, nx] of graph.get(now)) {
      if (!visited[idx]) {
        visited[idx] = true;
        path.push(nx);
        dfs(nx, path);
        path.pop();
        visited[idx] = false;
      }
    }
  };

  dfs("ICN", ["ICN"]);
  return answer;
}

 

1. 인접 리스트(`graph`)를 생성한다. `graph`는 Map 자료구조를 사용하고, key는 티켓의 출발지, value에는 `[tickets에서의 인덱스, 티켓의 도착지]`를 저장한다.

2. graph의 value들을 각각 도착지 오름차순으로 정렬한다. 이때 도착지는 문자열이기 때문에 비교 함수에 `localeCompare()` 메서드를 사용한다.

3. `dfs()`를 사용하여 재귀적으로 탐색하며 가능한 경로를 찾는다. 만약 가능한 경로를 찾는다면 바로 끝낼 수 있도록 answer에 값이 채워진 경우 return하도록 했다.