[Algorithm] 여행경로

📋 문제

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

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

 

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 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"]

 

 

✏️ 풀이

모든 경우의 수를 확인하기에는 공항의 수가 10000개가 될 수 있기 때문에 최악의 경우 10000! 라는 엄청나게 큰 수의 경우의 수가 나오므로 완전 탐색은 애초에 시작도 하지 않았다.

 

DFS를 돌리기 위해 출발지와 도착지가 들어있는 tickets 배열을 순회하며 그래프를 구성했다. 그래프는 출발지를 키로 가지고 도착지를 배열의 원소로 잡았다. 경로가 여러개인 경우 알파벳 순으로 제일 앞서는 값을 출력해줘야하기 때문에 그래프의 도착지 배열을 정렬해주며 도착지의 개수대로 사용한 항공권을 체크할 배열을 만들어줬다.

 

출발지는 무조건 인천(ICN)이므로 답이 될 임시 배열에 ICN를 넣어두고 현재 도시와 사용한 티켓수(cnt)를 인자로 넣어주며 DFS를 돌렸다. 만약 이미 사용한 항공권인 아닌 경우에만 임시 정답 배열에 도착지를 추가하고 체크배열에 체크한 이후 재귀 형식으로 DFS가 또 돌아간다. 돌다가 사용한 티켓의 수가 총 티켓의 수와 동일하다면 모든 티켓을 사용했다는 의미이므로 answer에 임시 정답배열을 할당한다. answer에 값이 입력된 이후에도 DFS가 돌아가는 것을 방지하고자 flag를 true,  false로 관리했다.

 

문제를 풀면서 맞는 로직인데도 불구하고 런타임 에러가 발생했었는데 현재 도시가 그래프 내에 출발지로 구성이 안되어있는 경우가 있는데 undefind를 for문으로 돌렸기 때문이었다. 그래프 내에 도착할 수 있는 경로가 없는 경우에는 return함으로써 돌고있는 DFS를 종료시켜주니 통과되었다.

 

⌨️ 코드

function solution(tickets) {
  var answer = [];
  const len = tickets.length;

  const graph = {};
  for (const ticket of tickets) {
    const [start, end] = ticket;
    if (!graph[start]) graph[start] = [end];
    else graph[start].push(end);
  }

  const check = {};
  for (const key of Object.keys(graph)) {
    graph[key].sort();
    check[key] = new Array(graph[key].length).fill(0);
  }

  const path = ['ICN'];
  let isFinish = false;
  const dfs = (city, cnt) => {
    if (!graph[city]) return; 

    for (let i = 0; i < graph[city].length; i++) {
      if (isFinish) return;

      if (!check[city][i]) {
        path.push(graph[city][i]);
        check[city][i] = 1;
        cnt += 1;

        if (cnt === len) {
          isFinish = true;
          answer = [...path];
          return;
        }

        dfs(graph[city][i], cnt);

        cnt -= 1;
        check[city][i] = 0;
        path.pop();
      }
    }
  };

  dfs('ICN', 0);

  return answer;
}