여행경로

여행경로

function deepCopy(obj) {
  return JSON.parse(JSON.stringify(obj));
}

function solution(tickets) {
  // dfs 순회를 위한 그래프 초기화
  const graph = {};
  tickets.forEach(([from, to]) => {
    if (!graph.hasOwnProperty(from)) {
      graph[from] = [to];
    } else {
      graph[from].push(to);
    }
  });

  // 알파벳순 정렬
  for (const vertex in graph) {
    graph[vertex].sort();
  }

  // flag는 dfs에서 정답이 도출될 경우 나머지 함수의 호출을 전부 취소하기 위함
  let flag = false;
  let result;

  function dfs(node, hash, route) {
    route.push(node);

    // 경로를 전부 순회
    if (route.length == tickets.length + 1) {
      result = route;
      flag = true;
      return;
    }

    // 목적지까지 도착하지 못하고 중간에 경로가 끊길 때
    if (!hash.hasOwnProperty(node)) {
      return;
    }
    
    const neighbors = hash[node];
    for (let i = 0; i < neighbors.length; i++) {
      if (flag) {
        return;
      }
      const neighbor = neighbors[i];
      const copiedHash = deepCopy(hash);
      copiedHash[node].splice(i, 1);
      dfs(neighbor, copiedHash, route.slice());
    }
  }
  dfs("ICN", graph, []);
  return result;
}

• 문제에서 '모든 도시를 방문할 수 없는 경우는 주어지지 않습니다'가 가장 헷갈리는 부분이었다.

• 이는 모든 도시를 방문할 수 있는 경우가 적어도 하나 있다는 것일 뿐, 어떤 경로로 가든 상관없이 모든 도시를 방문할 수 있다는 의미가 아니기 때문이다.

• 처음에 반복문으로 풀려다가 재귀로 전환할 수 밖에 없는 이유였다.

• 그리고 답을 이미 도출한 경우 나머지 dfs를 돌지 않게끔 할 수 있는 방법도 알 수 있었다.