[프로그래머스] Lv.3 여행경로 (자바스크립트)

 

 

*모든 코드는 Javascript로 작성합니다.

*코드는 참고용으로만 봐주세요!

 

---

문제

 

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

 

 

 

 

해결방법

 

< ICN에서 출발하여 dfs로 공항을 탐색한다. tickets 개수만큼 탐색을 진행했을 때 모든 edge가 탐색되었다면 빠짐없이 방문한 것이므로, 탐색 경로를 결과에 넣는다.> 

- dfs 인수: vertex, cnt

   vertex는 다음 탐색할 공항을 의미하고, cnt는 탐색을 진행한 횟수. 나중에 cnt == tickets.length일 때 dfs를 종료하고, 모든 edge가 탐색되었다면 그 경로를 저장해야 한다.

- dfs 바깥에는 각 ticket 사용 여부를 트래킹할 배열 check, 마지막에 조건에 부합할 경우 그 경로를 담을 배열 result가 필요하다.

- 탐색 종료 후 result에 담긴 모든 가능한 경로들을 알파벳 순서로 정렬하여, 첫 번째 요소를 반환한다.

 

 

 

 

 

코드

 

function solution(tickets) {         var answer = getOrders("ICN");          if (answer.length == 1) return answer[0]; //가능한 경로 하나뿐이라면 그 경로 반환.     else {         answer.sort(sortFunction); //여러 개일 경우 sort         return answer[0];     }          function sortFunction(a, b){ //정렬용 함수         for (let i = 0 ; i < a.length; i++){             if (a[i]!=b[i]){                 if (a[i] > b[i]) return 1;                 else if (a[i] < b[i]) return -1;             }         }     }          function getOrders(v){         var check = new Array(tickets.length);  //ticket 사용 여부를 체크하기 위한 배열         check.fill(0);         var result = []; //가능한 모든 경로들 담을 배열         var order = []; //방문힌 공항 순서(경로 하나) 담을 배열          function dfs(vertex, cnt){             if (cnt == tickets.length){                 if (!check.every((el)=>el==1)) return 0; //모든 티켓이 사용되지 않았다면 실패.                  else {                     var arr = [...order];                     arr.push(vertex);                     result.push(arr); //모든 티켓이 사용되었다면 result에 넣어줌.                  }             }             for (let i = 0; i < tickets.length; i++){                 if (tickets[i][0] == vertex && check[i] == 0){                     check[i] = 1;                     order.push(vertex);                     dfs(tickets[i][1], cnt+1);                     check[i] = 0;                     order.pop(vertex);                 }             }         }         dfs(v, 0);         if (result.length == 0) return 0;         return result;     }          return answer; }