프로그래머스 Level 3 여행경로 JavaScript 문제 풀이

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

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

 

 

✅ JavaScript 답안 입니다 더보기 클릭!

 

function solution(tickets) {
    let travel_route = [];
    let visit = Array(tickets.length).fill(false);
    tickets.sort();
    const length_ticket = tickets.length;
    function travel(current_position, cnt, route){
        if(cnt===length_ticket && travel_route.length === 0){
            travel_route = route;
            return;
        }
        for(let i=0; i < tickets.length; i+=1){
            const ticket = tickets[i];
            const departure = ticket[0];
            const landing = ticket[1];
            if(visit[i]) continue;
            if(departure === current_position) {
                visit[i] = true;
                travel(landing, cnt+1, [...route, landing]);
                visit[i] = false;
            }
        }
    }
    
    travel("ICN",0, ["ICN"]);
    
    return travel_route;
}

 

📌 해설

DFS 문제 입니다. 

- 주어진 항공권을 모두 사용함

- 모든 도시를 방문할 수 없는 경우는 주어지지 않음

- 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return

 

위 세가지 조건이 핵심 조건이라고 생각했습니다. 

 

function solution(tickets) {
    let travel_route = [];
    let visit = Array(tickets.length).fill(false);
    tickets.sort();
    const length_ticket = tickets.length;

travel_route 는 여행 경로를 담을 배열입니다. 

visit는 방문한 곳을 true, 방문하지 않았으면 false 를 담을 배열입니다. 

모두 false로 초기화 해줍니다. 

 

tickets 는 방문 가능할 경우 알파벳 순으로 먼저 오는 공항을 방문해야하기 때문에 sort로 정렬 부터 해줍니다. 

tickets의 길이를 length_ticket 에 담습니다.

 

 

function travel(current_position, cnt, route){
        if(cnt===length_ticket && travel_route.length === 0){
            travel_route = route;
            return;
        }
        for(let i=0; i < tickets.length; i+=1){
            const ticket = tickets[i];
            const departure = ticket[0];
            const landing = ticket[1];
            if(visit[i]) continue;
            if(departure === current_position) {
                visit[i] = true;
                travel(landing, cnt+1, [...route, landing]);
                visit[i] = false;
            }
        }
    }

dfs 함수입니다. 

티켓 전체를 다 탐색했다면 travel_route에 경로를 담고 return 합니다. 

티켓 전체를 다 탐색하지 않았다면 for 문에서 탐색을 진행합니다. 

 

만약 티켓의 이륙지점(departure)과 내가 현재 있는 지점(current_position)이 같다면 

visit[i]를 true 로 변경하고 다음 경로를 찾습니다 => travel( 착륙, cnt+1(티켓 갯수확인), 현재 까지 여행 경로); 

dfs 탐색이 종료되면 다른 여행 경로(node)를 탐색해야 하므로 기존까지의 visit를 초기화 해주는 과정이 필요합니다. 

travel 을 빠져나왔을때 visit 를 false로 변경해줍니다. 

 

 

 

::

 

level 3 을 풀어보니 확실히 어려운 느낌!

이제부터 level 2와 3을 적절히 섞어서 풀어보고 감을 익히면 좋을 것 같아요