프로그래머스 여행경로 자바스크립트

 

어렵게 접근해서 조금 헤맸다.

일반적인 dfs 경로 탐색과 유사하지만 '알파벳 순이 빠른 경로' 라는 조건때문에 어렵게 생각했다.

프로그래머스 문제는 명쾌하게 풀리는 편이라고 생각한다. 그러므로 너무 복잡하게 접근하지 않는 편이 좋을 것 같다.

중복 경로(같은 티켓이 또 들어오는 경우)인 케이스와 첫번째 정렬 경로로 모두 방문할 수 없는 경우

이 2가지를 고려하는 게 핵심이다.

function solution(tickets) {
    
    var answer = [];
    
    const map = [];
    const visited = [];
    
    for(let i = 0; i < tickets.length; i++){
        if(map[tickets[i][0]] === undefined){
            map[tickets[i][0]] = [];
            visited[tickets[i][0]] = [];
        }
        map[tickets[i][0]].push(tickets[i][1]);
        visited[tickets[i][0]].push(0);
    }
    
    const dfs = (air, br, k) => {
        
        
        if(k === tickets.length + 1 && answer.length === 0) {
            answer = [...br];
            return;
        }
        
        if(answer.length > 0)
            return;

        const arr = map[air];
        if(arr === undefined)
            return;
        
        arr.sort();
        for(let i = 0; i < arr.length; i++){
            if(visited[air][i] === 0){
                visited[air][i] = 1;
                br[k] = arr[i];
                dfs(arr[i], br, k+1);
                visited[air][i] = 0;
            }
        }
    }

 

같은 티켓이 또 들어오는 경우가 있기 때문에,

방문때마다 visited를 일반적인 공항이름을 넣거나 하면 같은 티켓을 탐색할 수 없다.

때문에 visited를 map과 동일한 배열을 만들어서 방문 체크를 진행했다.

한 경로에 탐색이 끝나고 해당 경로로 모든 경로를 방문할 수 없을 때를 위해

탐색이 끝나면 visited를 다시 방문하지 않은 것으로 되돌린다.