[알고리즘/프로그래머스/고득점Kit] 여행경로(DFS, JS)

문제

---

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

프로그래머스

 

풀이

---

주어진 항공권을 모두 이용해 여행경로를 짤 때, 방문하는 공항 경로를 구하는 문제이다. 이때 주의할 점은 가능한 경로가 여러 개 있다면, 알파벳 순서가 앞서는 경로를 반환해야 한다는 것이다. 

 

이 조건을 만족하기 위해 tickets 배열을 먼저 정렬해준다. 자바스크립트 sort는 기본적으로 알파벳 오름차순 순서로 배열을 해주고, 2차원 배열의 경우 첫 번째 요소가 같은 경우, 두 번째 요소를 기준으로 정렬해주므로 tickets.sort()를 하면 된다.

 

티켓 배열이 정렬된 상태이므로 처음으로 티켓을 모두 사용한 경우에 지나온 path가 정답이 된다. 이때 경로를 끝까지 탐색하고 돌아나오면서 완전탐색을 해야하므로 각 티켓을 사용했는지를 확인하는 체크 표시를 풀어주는 단계가 필요하다. 

function solution(tickets) {
    const N = tickets.length
    const ch = Array(N).fill(0)
    let answer = []
    
    tickets.sort()

    function DFS(cur, visitedCnt, path) {
        // 티켓 모두 사용한 경우 
        if (visitedCnt === N && answer.length === 0) {
            answer = path
            return
        }
        
        // 아닌 경우
        for (let i=0;i<N;i++) {
            const [from, to] = tickets[i]
            
            if (ch[i]) continue
            if (cur === from) {
                ch[i] = 1
                DFS(to, visitedCnt + 1, [...path, to])
                ch[i] = 0
            }
            
        }
    }
    
    DFS("ICN", 0, ["ICN"])
    return answer

}