코드

function solution(tickets) {
    let answer = []
    let visitedTicket = new Array(tickets.length).fill(false)
    
    dfs("ICN",["ICN"])
    
    return answer.sort()[0]
    
    function dfs(currentCity,path){
        if(path.length === tickets.length + 1){
            answer.push(path)
            return
        }
        tickets.forEach(([start,end],idx)=>{
            if(visitedTicket[idx]){
                return
            }
            
            if(start === currentCity){
                visitedTicket[idx] = true
                dfs(end,[...path,end])
                visitedTicket[idx] = false
            }
        })
    }
}

복기

간단한 dfs 문제인줄 알았는데 예외가 생각보다 까다로워 풀이에 시간이 많이 걸렸다

가장 고민됬던 부분이 "ICN"과 같이 문자열로 주어진 경우이기 때문에 방문이력을 어떻게 저장할지 고민이었다. 처음에는 {}나 Map을 사용해 문자열을 저장하기도 했었다. 하지만 나중에 로직이 복잡해지는 문제가 생겨 다른 사람의 코드를 참고하였다

해결은 간단했다. 주어진 tickets와 같은 길이의 배열을 만들고 해당 ticket이 사용되었다면 같은 idx에 true를 집어넣는다.

dfs 순회는 알고리즘 문제에서 많이 보이는 visited를 껐다켰다하는 패턴이다.

만약 사용하지 않은 ticket이라면 해당 ticket의 목적지를 기준으로 dfs를 순회한다

가지치기, 백트래킹 기준인 모든 ticket을 사용하는 경우에 answer 변수에 path를 담아준다

요약

1. dfs에서 중요한 visited를 어떻게 정의하고 사용할 지 잘 고민해보자