Skip to main content

작성일 : 2024.11.05

여행 경로 문제

문제 설명​

주어진 항공권을 모두 사용하여 여행 경로를 만드는 문제입니다. 시작점은 항상 "ICN" 공항이며, 가능한 경로가 여러 개일 경우 알파벳 순서가 앞서는 경로를 선택해야 합니다.

예시​

입력: [["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"]

제한 조건​

  1. 공항 정보
    • 3글자 알파벳 대문자
    • 3개 이상 10,000개 이하의 공항
  2. 티켓 정보 ([출발, 도착])
    • 모든 티켓 사용 필수
    • 불가능한 경로는 주어지지 않음

해결 코드​

function solution(tickets) {
  var answer = [];
  let usedT = new Array(tickets.length).fill(false);
  tickets.sort();

  const dfs = (nowCity, route) => {
    if (usedT.indexOf(false) == -1 && answer.length == 0) {
      answer = route;
      return;
    }
    for (let i = 0; i < tickets.length; i++) {
      const [start, end] = tickets[i];
      if (!usedT[i] && start == nowCity) {
        usedT[i] = true;
        dfs(end, [...route, end]);
        usedT[i] = false;
      }
    }
  };

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

알고리즘 설명​

  1. 초기화 및 정렬
let usedT = new Array(tickets.length).fill(false); // 티켓 사용 여부
tickets.sort(); // 알파벳 순서 보장
  1. DFS 구현
const dfs = (nowCity, route) => {
  // 모든 티켓 사용 && 아직 경로 미저장
  if (usedT.indexOf(false) == -1 && answer.length == 0) {
    answer = route;
    return;
  }

  // 가능한 다음 경로 탐색
  for (let i = 0; i < tickets.length; i++) {
    const [start, end] = tickets[i];
    if (!usedT[i] && start == nowCity) {
      usedT[i] = true; // 티켓 사용
      dfs(end, [...route, end]); // 다음 도시로 이동
      usedT[i] = false; // 티켓 반환
    }
  }
};

구현 포인트​

  1. 알파벳 순서 처리

    • tickets 배열을 미리 정렬
    • 첫 번째 유효한 경로가 알파벳 순서가 가장 앞선 경로

  2. 백트래킹

    • 티켷 사용 표시 및 복구
    • 모든 가능한 경로 탐색

  3. 경로 저장

    • 첫 번째 완성된 경로만 저장
    • 모든 티켓 사용 확인

주요 메서드 설명​

  1. 배열 메서드
Array(n).fill(false); // 사용 여부 배열 초기화
array.sort(); // 알파벳 순 정렬
array.indexOf(false); // 미사용 티켓 확인
  1. 구조 분해 할당
const [start, end] = tickets[i]; // 티켓 정보 분해

시간 복잡도​

  • O(n!): n은 티켓의 수
  • 모든 가능한 경로를 탐색

공간 복잡도​

  • O(n): n은 티켓의 수
  • 사용 여부 배열과 재귀 호출 스택

예외 처리​

  1. 가능한 경로가 여러 개인 경우
    • 정렬을 통해 알파벳 순서가 앞선 경로 선택
  2. 경로 완성 조건
    • 모든 티켓 사용
    • 이전에 저장된 경로 없음