[프로그래머스] 여행경로 / JavaScript / Level 3

🚩문제 주소

📄풀이

백트래킹

문제를 해석했을 때 그래프가 만들어지는 것 같아서 그래프 탐색 방법을 활용하여 풀어보았습니다.
그 중 백트래킹 알고리즘을 활용하면 좋을 것 같았습니다.

1. 주어진 항공권 수 만큼 방문 확인 배열을 만들고, 종료 변수를 항공권 갯수 +1로 선언합니다.

2. backTracking 함수

   • 현재 여행 경로의 길이와 종료 변수가 같아지면 정답 배열에 여행 경로를 넣고 종료합니다.
   • 주어진 여행 경로를 순회하여 사용한 적이 없는 항공권이라면 항공권의 출발지와 도착지를 분리합니다.
     현재 여행 경로의 마지막 지점과 항공권의 출발지가 같다면 방문 확인을 해주고 backTracking 함수에 도착지를 넣고 호출합니다.

3. 정답 배열을 오름차순으로 정렬한 뒤 첫 번째 배열을 반환합니다.

👨‍💻코드

const solution = (tickets) => {
  const answer = [];
  const visited = Array(tickets.length).fill(0);
  const finished = tickets.length + 1;

  const backTracking = (travelPath) => {
    if (travelPath.length === finished) {
      answer.push(travelPath);
      return;
    }
    tickets.forEach((ticket, i) => {
      if (!visited[i]) {
        const [start, end] = ticket;
        if (travelPath.at(-1) === start) {
          visited[i] = 1;
          backTracking([...travelPath, end]);
          visited[i] = 0;
        }
      }
    });
  };
  backTracking(["ICN"]);

  return answer.sort()[0];
};