(JS) Programmers : 여행경로 (DFS)

코딩테스트 연습 - 여행경로 | 프로그래머스 스쿨

프로그래머스

문제를 풀기위해 아래와 같은 요소들을 고려하였다.

1. tickets에 sort를 먼저 적용하여 가장 빠르게 나오는 답변이 알파벳 순이 될 수 있도록 했다.
2. 조합을 생성하여 가장 적합한 결과를 찾아야하므로 DFS를 활용했다.

function solution(tickets) {
    tickets.sort();
    let result = [];
    let visited = Array(tickets.length).fill(false);

    function dfs(airport, visited) {
        if (airport.length === tickets.length + 1) {
            result.push(airport);
            return true;
        } else {
            for (let i = 0; i < tickets.length; i++) {
                let [from, to] = tickets[i];
                if (visited[i] === false && airport[airport.length - 1] === from) {
                    visited[i] = true;
                    airport.push(to);

                    if (dfs(airport, visited)) {
                        return true;
                    }

                    visited[i] = false;
                    airport.pop();
                }
            }
        }
        return false;
    }

    dfs(["ICN"], visited);
    return result[0];
}

 

 

1. tickets에 sort() 활용

모든 공항을 방문하는 경우의수가 여러개 존재할 경우 알파벳 순으로 앞서는 케이스를 답변으로 제출해야한다.

모든 경우의 수를 계산한 뒤 알파벳 순서상 가장 앞선 결과를 제출하는 방법도 있지만 이 경우 DFS가 모든 경우의 수를 검토해야한다는 단점이 존재한다.

 

따라서 tickets 배열 자체를 정렬한 뒤 DFS를 사용하여 가장 먼저 발견되는 경우의수를 답변으로 제출하도록 했다.

 

 

2. DFS 활용

모든 티켓을 사용해야 한다는것이 조건(트리의 정점까지 도달해야함)이므로 깊이 우선 탐색을 활용했다.

사용한 값들의 용도는 다음과 같다.

 

• airport : DFS의 stack 역할. 사용가능한 티켓을 발견할 경우 도착지가 지속적으로 추가됨.
• visited : DFS 재귀 과정에서 이미 사용한 티켓 구분을 위한 배열. 초기에는 티켓길이만큼 false로 채워져있음
• from : 재귀 과정에서 현재 연산중인 티켓의 출발지
• to : 재귀 과정에서 현재 연산중인 티켓의 도착지

 

DFS 함수내의 내용을 정리하면 다음과 같다.

1. 결과값 도출을 위한 airport 배열 길이 확인 : airport 배열 길이가 tickets배열길이+1 일경우 모든 ticket을 사용한 유효한 결과이므로 result 배열에 저장한 뒤 함수를 종료한다.
2. 티켓 사용 과정 시작 : 위 조건에 해당하지 않을경우 tickets 배열에 있는 내용을 순차적으로 airport 배열에 추가한다. 추가조건은 아래와같다.
   조건 1) visited 배열의 현재 ticket과 매치되는 값이 false. (index 기준)
   조건 2) airport 배열의 마지막 값(마지막으로 추가한 ticket의 도착지)과 현재 추가하는 ticket의 출발지가 같아야함.
3. DFS 방문 처리 : 티켓을 사용했으므로 visited의 값을 true로 변경한다.
4. DFS 재귀 : 값이 수정된 airport 배열과 visited 배열을 이용해 dfs 함수를 재귀한다.
5. 백트래킹을 위한 값 복구 : 재귀 호출이 종료된 뒤 visited를 다시 false로 변경하고 airport 배열의 마지막 값을 제거한다.
6. 티켓 사용 과정의 재귀 : 2~5을 반복하며 1번에 충족하는 결과값을 찾는다.