문제 링크

프로그래머스 문제

풀이

처음에는 dfs로 풀었으며, 가장 먼저 발견한것을 종료 조건으로 걸었을때,
발생한 문제는, 알파벳 순서로 도착하기 위해서인데,
해당 문제를 해결하기 위해서 for문의 배열의 순서를 tickets.를 sort 함으로서 해결하였다.

코드

// dfs풀이
function solution(tickets) {
    var answer = [];
    
    const AllCity = tickets.length+1;
    const visited = new Array(tickets.length).fill(false);
    tickets = tickets.sort( (a,b) => { // 알파벳 순서로 먼저 방문하기 위해서 사용합니다.
            if(a[1] > b[1]){
                return 1
            }else{
                return -1
            }
    })
    

    let findAnswer = false;
    const dfs = (curCity , visitedCity) => {
        // 종료 조건
        if(findAnswer) return;
        if(visitedCity.length === AllCity){
            findAnswer = true //  bfs 처럼 가장 먼저 발견한걸로 종료
            answer = visitedCity
            return ;
        }
        
        // 다음으로 넘어가는 조건
        
        for(let i=0; i< tickets.length; i++){
            if(tickets[i][0] === curCity){
                 // 없어야만
                if(!visited[i])
                    {   
                        visited[i] = true
                        
                        dfs(tickets[i][1] , [...visitedCity,tickets[i][1] ])
                        visited[i] = false
                    }
            }
        }
    }
    
    dfs("ICN",["ICN"])
    
    
    return answer;
}