[JavaScript] 프로그래머스 코딩테스트 레벨 3 : 여행 경로

📌  문제

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

📌  제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

📌  입출력 예

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

---

📌  풀이

알아야 하는 것

• 주어진 항공권을 '모두' 사용해 여행 경로를 짤 때, ICN과 이어진 모든 공항을 경유하는 문제로 DFS로 접근해보기로 했다.
• 출발지를 키값으로, 도착지를 밸류값으로 한 객체를 만들거나 Map을 만들어 그래프를 구현한다. 

구할 것

1. 스택으로 풀기

• 그래프
  • 출발지와 도착지를 순회하면서 그래프에 출발지를 키값으로 하는 밸류값이 없다면 빈 배열을 만들어 넣어주고, 이미 출발지를 키값으로 하는 밸류값이 있다면 거기에 새로운 밸류값(지금 순회한 밸류값)을 push한다.
  • 문제에서 가능한 경로가 2개 이상일 경우 알파벳 순서대로 가야 한다고 하니 출발지를 키값으로 하는 밸류값들을 sort해준다.
• stack 구현
  • stack과 정답을 반환할 route라는 배열을 선언한다. 스택에는 무조건 처음에 문제에서 주어진대로 "ICN"이 들어가야 한다. 스택을 구현하는 것과 똑같이 스택의 가장 최근 값을 from으로 할당했을 때, 1) 해당 출발지를 키값으로 그래프에 밸류값이 있다면 shift()로 앞부터 stack에 push한다. 2) 만약 출발지에 도착지가 없는 경우나 1번 과정을 거쳐 출발지를 키값으로 하는 밸류값의 길이가 0일 때  route에 stack.pop()을 push한다.
  • 1번의 경우 이름 순으로 넣기 위해서 shift()로 현재 출발지에서 갈 수 있는 도착지를 stack에 넣어준 것이다.
  • 2번의 경우 중에서도 출발지에 도착지가 없는 경우는  ["ICN", "JFK"],  ["SFO", "ICN"], ["JFK", "HND"], ["ICN", "SFO"] 이런 경우다. 이럴 땐 지금 이 값을 나오게 한 stack.pop을 push하는 것이다. 1번 과정을 거쳐 도착지의 길이가 0인 경우는 앞에서 shift로 값이 잘려 나가기 때문이다.
• 이렇게 stack이 돌아갈 때 길이가 0이 된다면 멈추게 되는데, 이 때 route에 들어간 순서는 처음에 이름 순으로 들어갔기 때문에 먼저 들어간 이름이 가장 밑에 깔려 있다. 즉 이름 순을 만들려면 route를 뒤집어 줘야 한다. 따라서 reverse()를 사용해 뒤집어준다.

function solution(tickets) {

// 그래프 구성 (키값을 기준으로 밸류값 확인 & 알파벳 순으로 정렬)
  const graph = {};

  for (let [from, to] of tickets) {
    if (!graph[from]) {
      graph[from] = [];
    }
    graph[from].push(to);
  }

  for (let from in graph) {
    graph[from].sort();
  }

  const route = [];
  const stack = ["ICN"];

  while (stack.length > 0) {
    const from = stack[stack.length - 1];

    if (!graph[from] || graph[from].length === 0) {
      route.push(stack.pop());
    } else {
      stack.push(graph[from].shift());
    }
  }
  return route.reverse();
}

 

2번째 예시로 간단하게 확인해보자.

2. 재귀함수로 풀기

• 그래프
  • 동일하게 구성해도 되는데 맨 처음에 접근한 방식은 Map이었다. 그냥 객체로 그래프 만드는 것과 크게 다르진 않다; 근데 처음에 스터디원 분들이 해시맵으로 접근하셨던 게 생각나서 써보긴 했다.
• 재귀함수 구현
  
  • ICN의 밸류값들을 destinations에 할당했다. 위 코드에서 아닐 경우 조건을 반대로 뒤집어서 destinations이 있고, 길이가 0보다 클 때 while문을 돌린다. 이 때 next는 도착지의 앞부터 잘라 가져가는데 이 부분이 다 잘려서 while문 조건에 맞지 않으면 dfs는 종료되는 구조다.
  • 이렇게 하면 처음에 ICN -> ATL로 시작하는 재귀함수 시작 -> ICN으로 시작하는 재귀함수 시작 -> SFO로 시작하는 재귀함수 시작 -> ATL로 시작하는 재귀함수 시작 -> SFO로 시작하는 재귀함수 시작 -> 종료 -> 종료 -> 종료 모든 재귀함수가 종료된다. 종료될 때마다 route에 시작 값을 넣게 했으니 가장 먼저 종료된 SFO를 시작으로 route = ["SFO", "ATL", "SFO", "ICN", "ATL", "ICN"]이 나오게 된다.
  • stack에 넣으면 LIFO, 마지막에 넣은 것들이 먼저 나오다 보니 우리가 원하는대로 ICN를 시작으로 보여주려면 이 구조를 뒤집어줘야만 한다. 

function solution(tickets) {
  const graph = new Map();

  // 그래프 생성
  for (let [from, to] of tickets) {
    if (!graph.has(from)) {
      graph.set(from, []);
    }
    graph.get(from).push(to);
  }

  // 도착지 정렬
  for (let destinations of graph.values()) {
    destinations.sort();
  }

  const route = [];

  function dfs(start) {
    const destinations = graph.get(start);

    while (destinations && destinations.length > 0) {
      const next = destinations.shift();
      dfs(next);
    }

    route.push(start);
  }

  dfs("ICN");

  return route.reverse();
}

 

한 문제인데 엄청 알차게 풀었다;