[Programmers]여행경로/JS

문제링크

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

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/43164%5D)

풀이방법

"만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다" 라는 조건이 존재하기 때문에

입력받은 tickets를 정렬해주었다.

JS에서 sort 함수를 사용하면 알아서 사전 순 정렬을 해준다. 신기하게 2차원 배열도 우리가 원하는 결과대로 정렬해준다.

 

항상 "ICN"에서 출발하기 때문에 answer 배열에 "ICN"을 넣어준다.

 

이후는 주석에 적어둔 로직대로 작동한다.

정답코드

function solution(tickets) {
    var answer = [];
    let visit = new Array(tickets.length).fill(false);    // 방문 여부 저장
    let sortedTickets = tickets.sort();    // 티켓 사전순으로 정렬
    let len = sortedTickets.length;

    answer.push("ICN");    // 항상 "ICN"에서 출발

    const DFS = (str) => {    
      for(let i=0;i<len;i++){
          if(!visit[i] && str == sortedTickets[i][0]){    // 방문하지 않았고 가능한 경로일 때
              answer.push(sortedTickets[i][1]);    // answer 배열에 넣어주고
              visit[i]=true;    // 방문 처리 해줌
              DFS(sortedTickets[i][1]);    // DFS 재귀호출
              if(answer.length == len+1) return;    // 모두 방문한 경우 종료시킬 조건
              visit[i]=false;    // 탐색에 실패한 경우 방문하지 않음으로 처리
              answer.pop();    // answer 배열에서 삭제
          }
      }
    }

    DFS("ICN");

    return answer;
}

 

시행착오

먼저 실패했던 코드부터 보자.

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

    answer.push("ICN");
    const DFS = (str) => {    
        if(answer.length === len+1) return;
        
        for(let i=0;i<len;i++){
            if(!visit[i] && str == sortedTickets[i][0]){
                answer.push(sortedTickets[i][1]);
                visit[i]=true;
                DFS(sortedTickets[i][1]);
            }
        }
    }
    
    DFS("ICN");
    
    return answer;
}

위의 성공했던 코드와 비교해서 보자면

1. 탐색에 실패했을 때를 생각하지 않았다.
2. 탈출 구문( if(answer.length == len+1) return; )의 위치가 바뀌었다. 

탐색에 실패했을 때를 생각해서 방문하지 않음으로 처리해주고, answer 배열에서 삭제해줬다.

그리고 탈출 구문을 옮김으로써 문제를 해결했다.