[프로그래머스] 여행경로

문제 정보

• 프로그래머스 문제 링크
• 난이도 : level 3

 

해결 방법

노드 사이에서 관계를 가지고 있으므로 자료 구조는 그래프를 사용하고 탐색하는 방법은 BFS 혹은 DFS 를 사용하여 풀 수 있습니다. 해당 문제에서는 모든 공항을 방문해야 하므로 DFS 를 사용했습니다.

 

소스 코드

function solution(tickets) {
    let answer = [];

    const visitedList = [];
    const visited = new Array(tickets.length);
    const vAirport = [];
    visited.fill(false);

    const dfs = function(tickets, cur, depth){
        
        // 종료조건
        if(depth == tickets.length){
            vAirport.push(cur);
            visitedList.push(JSON.parse(JSON.stringify(vAirport)));
            
            // 한개의 visitedAirport 변수를 사용하기 때문에 
            // pop 해주지 않으면 다음번에 visitedList 에 추가로 쌓임
            vAirport.pop();
            return;
        }

        // 순회
        for(let idx = 0; idx < tickets.length; idx++){
            if(tickets[idx][0] === cur && !visited[idx]){
                visited[idx] = true;
                vAirport.push(cur);
                
                //console.log(`vAirport:${vAirport}`);
                dfs(tickets, tickets[idx][1], depth + 1);

                visited[idx] = false;
                vAirport.pop();
            }
        }        
    };
    
    dfs(tickets, "ICN", 0);

    // 정렬
    visitedList.sort();

    for(let idx = 0; idx < visitedList.length; idx++){
        //console.log(`visitedList[${idx}]:${visitedList[idx]}`);
    }

    answer = visitedList[0];

    return answer;
}

DFS 내부는 종료 조건을 기술한 부분과 cur 라는 현재 공항에서 갈 수 있는 다음 공항을 탐색하는 2가지 부분을 구현했습니다. 알파벳 순으로 앞서는 경로라는 제한 조건이 있어서 visitedList 에 방문하는 공항경로의 전체 정보를 가지고 정렬하여 답을 도출합니다.

 

생각해볼 문제

• 공항 수가 10,000개 이하인데 현재 공항에서 다음 공항으로 갈 곳을 순회하는 방식에 문제가 없는지 확인이 필요할 것 같습니다. 그럴 경우 모든 도시를 방문할 수 없는 경우를 초기에 제거하는 방법에 대한 고려가 필요할 것으로 보입니다.

 

참고 자료

• [알고리즘] 그래프의 깊이 우선 탐색 DFS