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

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

코딩테스트 연습 - 여행경로

 

그동안 이해가 안됬었던 bfs, dfs가 조금씩 이해가 가는거 같다.. 감동.. ㅠㅠ

이 문제에서 중요한 것은, 모든 티켓을 순회하게 하는 것이 목적이다. 지금은 dfs로 풀이를 할 계획이다.

플로우는 다음과 같다

1. 방문경로를 체크하기위한 visited를 만든다.

2. dfs 함수를 만든다. 함수의 변수는 depth와, ticket list의 index를 받는다.

3. dfs에서, 다음 티켓위치와, visited가 false라면 visited를 true로 만들고 dfs를 출력시킨다. 이때, dfs출력 후, 조건을 만족하지 않았다면 다시 visited를 false 시킨다

4. 그리고 ICN을 첫 티켓으로 answer에 넣는다. ICN도, 3번과같이 방문조건이 완성되지 않는다면 visited false를 넣는다.

(방문 조건이란? 모든 위치를 방문했을 경우입니다, 누가 만든용어가 아니라, 제가 여기서 방문 완료 조건이 지금 문제풀이에 필요해서 이 단어를 썼습니다)

function solution(tickets) {
    const sortTicket = tickets.sort((a,b)=> {if(a[1]>b[1]){return 1}
                                            if(b[1]>a[1]){return -1}  })
    const answer = ["ICN"]
    const visited = Array.from({length:sortTicket.length}).map((v)=>false)
    function dfs(depth, num){
        const [from, to] = sortTicket[num]
        if(depth===sortTicket.length-1){
            answer.push(sortTicket[num][1])
            return
        }
        for(let i=0;i<sortTicket.length;i++){
            if(sortTicket[i][0]===to && visited[i]===false){
             visited[i]=true;
             answer.push(sortTicket[i][0])
             dfs(depth+1, i);
             if(answer.length<sortTicket.length){
             visited[i] = false;
             answer.pop()}
            }
        }
    }
    for(let i =0;i<sortTicket.length;i++){
        if(sortTicket[i][0]==="ICN"){
            visited[i]=true
            dfs(0, i)
            visited[i]=false
        }
    }
    return answer
}

문제를 풀면서 가장 힘든 반례는

ICN AOO, ICN BOO, BOO ICN, 와 같이, ICN이 겹치는 상황에서 더빠른 글자로 갈 경우 방문조건을 만족하지 않는 경우가 있어서, 처음에 좀 헤맸던거 같습니다. 이 문제에서는 굳이 맨위의 sort를 사용하지 않아도 됩니다.