[Programmers] 여행경로


  • 프로그래머스 여행경로 문제 풀이입니다.

  • 해당 문제에서 가장 중요한 것은 새로운 경로를 계속해서 전달해주어야 하는 것이다

  • dfs 관련 문제에서 내가 이미 도착한 곳을 visited라는 배열안에 넣고 해당 배열에 있는 곳은 다시 찾아가지 않도록 처리해주는 경우가 많다

  • 하지만 해당 문제의 경우에는 이미 온 곳을 다시 돌아간 뒤 새로운 경로를 찾아야 하기 때문에, 새롤운 경로를 전달해주어야 한다

// 전체 경로를 저장하기 위한 배열
let routes = [];

function solution(tickets) {
  for (let i = 0; i < tickets.length; i++) {
    if (tickets[i][0] === "ICN") {
      console.log("start", tickets[i]);
      const newTickets = [...tickets];
      newTickets.splice(i, 1);
      // console.log('newTickets', newTickets)
      dfs(tickets[i][1], [...tickets[i]], newTickets);
    }
  }

  routes.sort(); // 알파벳 순서대로 정렬해준다
  return routes[0];
}

function dfs(current, route, tickets) {
  // 더 이상 갈 수 있는 경로가 없는 경우
  if (tickets.length === 0) {
    routes.push(route);
    return;
  }

  // 배열 destructuring으로 비교해준다
  tickets.forEach(([departure, destination], idx) => {
    if (current === departure) {
      // 새로운 경로 계산
      const newTickets = [...tickets];
      newTickets.splice(idx, 1);

      dfs(destination, route.concat(destination), newTickets);
    }
  });
}

Reference









© 2020. by dkmqflx

Powered by dkmqflx