[코딩테스트 javascript] 여행경로 - BFS,DFS , 그래프 탐색 알고리즘, 너비탐색알고리즘,깊이탐색알고리즘

여행경로

 

 

프로그래머스

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

 

풀이 1 - 50점

1. 최단거리는 BFS 즉, Queue를 이용한다.

2. tickets 배열을 정렬한 후 ICN으로 출발하는 요소부터 시작한다.

3. queue를 이용하여 BFS 를 한다.

function solution(tickets) {
    // 알파벳순 정렬
    tickets.sort()
    console.log(tickets)
    //queue
    let queue = [];
    let visit = tickets.map(v=>false)
    let answer = [];
    const start = tickets.filter(v=>v[0]==="ICN")
    let index = tickets.indexOf(start[0])
    console.log(visit[index]=true)
    queue.push(tickets [index])
    
    while(queue.length) {
        
        const [cur,arrived] = queue.shift()
        answer.push(cur)
        for (let i=0;i<tickets.length;i++) {
            if (arrived===tickets[i][0]&&!visit[i]) {
                visit[i]=true;
                queue.push(tickets[i])
                break;
            }
            if(i===tickets.length-1) answer.push(arrived)
        }
    }
    
    return answer;
}

 

 

틀린 이유:

테스트 케이스 ["ICN", "A"],["ICN", "B"],["B", "ICN"] 일때  ['ICN', 'A']만 나온다.

이는 주어진 조건 중 "주어진 항공권은 모두 사용해야 합니다."에 위반된다.

 

위 코드에서 도착지로 시작하는 티켓이 없을 때의 경우를 제거하지 않았기 때문에 발생한 문제이다. 

 

 

풀이 2

1. DFS, 즉 재귀함수를 이용해서 문제를 해결한다.

- start점이 2개 이상인 경우가 있으므로 재귀함수로 푸는 것이 적절하다.

2. DFS(티켓 , 출발지 ,  리턴값)으로 재귀함수 설정

- 티켓 배열을 하나씩 줄여가면서 리턴값을 answer 배열에 push한다.

3. DFS 함수 생성

- 종료 조건은 ticket 배열의 길이가 0이 될때이다.

- 수행 동작은 ticket 배열을 돌면서 출발지가 같은 것이 있을 때 마다 함수를 반복한다.

- 이때, 매개변수는 배열을 splice 해주고, 출발지는 arr[i][1]이며, str에 arr[i][1]를 더한 것이다.

 

 

 

function solution(tickets) {
    let answer = [];
    DFS(tickets,'ICN',["ICN"]);
    return answer.sort()[0];
    
    function DFS(arr,start,str){
        // console.log("DFS t,start,str : ["+arr+"],["+start+"],["+str+"]")
        //1. 종료조건
        if(arr.length == 0){
            answer.push(str)
            // console.log("answer",answer)
        }
        //2. 수행동작
        for(let i in arr){
            if(arr[i][0] == start){
                let tmp = arr.slice();
                tmp.splice(i,1);
                // console.log(tmp.splice(i,1))
                let tmp2 = str.slice();
                // console.log(str+"\n");
                tmp2.push(arr[i][1]);
                DFS(tmp,arr[i][1],tmp2)
            }
        }
    }
}