[JS] 여행 경로

graph + 백트래킹을 활용하여 해결하였다.

 

 

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

프로그래머스

 

먼저 그래프에 티켓들을 담는다. 이때 dfs를 활용해서 티켓의 정보를 가져오는 경우에 정렬이 되어있어야 하므로 마지막에 그래프를 정렬해준다.

 

이후 dfs를 활용하여 티켓을 탐색한다. dfs의 종료조건이 해당나라의 방문이 아닌 티켓의 사용 유무인 점을 알아두자.

 

 

따라서 티켓을 찢고 -> DFS 검색하고 -> 만약 해당 경로가 답이라면 그게 제일 빠르므로 종료 -> 그렇지 않다면 티켓을 복구한 후 다음 티켓을 사용처리

 

이런 흐름을 따라서 검색을 하고 정답은 백트래킹을 활용해서 만들어나갔다.

 

 

 

 

function solution(tickets) {
    const graph = new Map()
    // 그래프에 티켓정보 담기
    for (const [start,end] of tickets){
        if(graph.has(start)) graph.get(start).push(end)
        else graph.set(start,[end])
    }
    //그래프 정렬
    for (const [start,ends] of graph){
        graph.set(start,ends.sort())
    }
    
    const dfs = (city,cnt) => {
        // 모든 티켓을 다 쓴경우 정답이므로 도시 반환
        if(cnt===tickets.length) return [city]
        // 더이상 갈곳이없는경우 빈배열을 반환
        if(!graph.get(city)) return []
        // 다음 도시들 가져와서 깊은복사
        const nxCities = [...graph.get(city)]
        
        for (let i=0;i<nxCities.length;i++){
            // 해당 티켓을 사용처리 (idx를 사용해서 중복티켓이어도 1장만 사라지게)
            graph.set(city,nxCities.filter((_,idx)=>idx!==i))
            const ret = dfs(nxCities[i],cnt+1)
            // 티켓을 다시 사용안한걸로 처리
            graph.set(city,nxCities)
            // 결과로나온 배열길이 + cnt가 티켓 수라면 정답인것
            if(ret && ret.length+cnt===tickets.length) return [city,...ret]
        } 
        
    }
    
    return dfs('ICN',0)
}