알고리즘 문제 풀이(프로그래머스 - 여행경로)

프로그래머스 LEVEL 3(여행경로)

• 사용 언어 : javascript

• 해결 날짜 : 2022-10-24

• 해결 방법 :
  • 출발지인 인천으로부터 도착지까지의 경로를 전부 경유해야 하기 때문에 dfs를 사용하는게 나을 것 같아서 dfs 사용
  • 출발지-도착지 쌍을 방문하지 않은 경우
    • 방문 처리
    • 도착지를 출발지로 선택, 현재까지의 경로, count + 1을 dfs를 사용해 재귀
    • 방문 처리 취소
  • 경로를 잘 선택하여 모든 경로를 경유한 경우, answer과 비교하여 작은 값 answer에 업데이트 후 dfs 종료
• 회고 :
  • 처음에 방문 여부를 저장하기위해 ‘출발지, 도착지’를 key로 갖는 객체를 생성했는데 더 간단한 방법이 존재
  • 전체 경로를 비교할 때 join(‘’) 후 비교했는데 안돼서 헤맴

• 코드

  function solution(tickets) {
      const visited = Array.from({length: tickets.length}, () => false);
      let answer = [];
          
      const dfs = (from, route, count) => {
          if (count === tickets.length) {
              if (!answer.length || answer.toString() > route.toString()) answer = route;
              return;
          }
              
          for (let i = 0; i < tickets.length; i++) {
              if (!visited[i] && from === tickets[i][0]) {
                  visited[i] = true;
                  dfs(tickets[i][1], [...route, tickets[i][1]], count + 1);
                  visited[i] = false;
              }
          }
      }
          
      dfs('ICN', ['ICN'], 0);
          
      return answer;
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges