[프로그래머스] DFS/BFS > 여행경로 /JS / 접근법, 문제풀이

문제 설명

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

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

제한사항

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

입출력 예

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=javascript

---

 

🔹 코드

      
      
      
    
function solution(tickets) {
    const visited = Array.from({length: tickets.length}, () => false); // 방문한 티켓을 체크하는 배열
    let arr = ['ICN']; // 현재까지의 경로를 저장하는 배열
    let result = []; // 가능한 경로 중 사전순으로 앞선 경로를 저장

    function DFS(departure, count) {
        // 모든 티켓을 사용한 경우, 결과를 갱신
        if (count === tickets.length) {
            if (result.length) { // 이미 저장된 결과가 있다면 비교
                for (let i = 0; i < result.length; i++) {
                    if (result[i] !== arr[i]) {
                        if (result[i] > arr[i]) result = arr.slice(); // 사전순으로 더 작은 경우 업데이트
                        return;
                    }
                }
            } else {
                result = arr.slice(); // 첫 번째 결과 저장
            }
        }
        
        for (let i = 0; i < tickets.length; i++) {
            const [from, to] = tickets[i];
            if (from === departure && !visited[i]) { // 출발지가 같고 아직 방문하지 않은 티켓이라면
                visited[i] = true; // 방문 체크
                arr.push(to); // 경로 추가
                DFS(to, count + 1); // 다음 공항으로 DFS 탐색
                arr.pop(); // 백트래킹: 탐색 후 원상복구
                visited[i] = false; // 방문 해제
            }
        }
    }
    
    DFS('ICN', 0); // DFS 탐색 시작
    return result;
}

기존 코드의 문제점

1. 사전순 정렬이 이루어지지 않음
   • 현재 코드는 DFS 탐색 도중에 경로를 비교하여 사전순으로 앞선 경로를 찾으려 하지만, 미리 정렬한 후 탐색하는 것이 더 효율적입니다.
2. 불필요한 result 비교 로직
   • result와 arr을 일일이 비교하면서 갱신하는 방식이 비효율적입니다.
   • DFS를 사전순으로 탐색하면 불필요한 비교 없이 첫 번째로 찾은 경로가 정답이 됩니다.
3. 탐색 순서를 정렬하여 불필요한 연산 줄이기
   • tickets를 미리 정렬해두면, 가장 먼저 발견되는 경로가 사전순으로 앞서는 경로가 됩니다.
   • 이를 통해 result를 계속 비교하지 않아도 됩니다.

---

2. 개선된 코드 (최적화된 DFS 방식)

      
      
      
    
function solution(tickets) {
    // 티켓을 사전순으로 정렬 (출발지를 기준으로, 같다면 도착지 기준)
    tickets.sort();
    
    const visited = Array(tickets.length).fill(false);
    const result = [];
    
    function DFS(departure, path) {
        if (path.length === tickets.length + 1) { // 모든 티켓 사용 완료 시
            result.push([...path]); // 깊은 복사 후 저장
            return;
        }

        for (let i = 0; i < tickets.length; i++) {
            const [from, to] = tickets[i];
            
            if (!visited[i] && from === departure) { // 출발지가 일치하고 방문하지 않은 티켓일 경우
                visited[i] = true;
                path.push(to);
                DFS(to, path);
                path.pop(); // 백트래킹: 원상복구
                visited[i] = false;
            }
        }
    }

    DFS("ICN", ["ICN"]);
    return result[0]; // 사전순으로 가장 앞선 경로 반환
}

개선된 코드의 장점

1. 티켓을 미리 정렬하여 탐색 순서 최적화
   • tickets.sort();를 통해 미리 정렬하면, DFS 탐색 시 첫 번째로 찾는 경로가 정답이 됩니다.
   • 불필요한 비교 연산을 제거하여 코드가 더 효율적입니다.
2. 불필요한 result 갱신 제거
   • DFS에서 result를 비교하여 갱신하는 기존 방식 대신, 첫 번째로 탐색된 경로를 반환하는 방식으로 변경.
   • 코드가 더욱 직관적이며 유지보수하기 쉬움.
3. 시간 복잡도 감소
   • 기존 코드에서는 탐색 중 result를 비교하는 불필요한 연산이 많았음.
   • **정렬(O(N log N)) + DFS 탐색(O(N!))**으로 최적화하여 탐색 횟수를 줄임.

---

3. 정리 및 결론

이 문제는 DFS를 이용하여 여행 경로를 찾는 문제입니다. 하지만 사전순으로 앞서는 경로를 반환해야 하므로, 탐색 순서를 정렬하는 것이 핵심입니다.

• 기존 코드는 탐색하면서 경로를 비교하는 방식이었지만, 탐색 순서를 미리 정렬하면 불필요한 연산을 줄일 수 있습니다.
• 최적화된 코드에서는 tickets를 정렬하고, 정렬된 순서대로 DFS 탐색을 진행하여 가장 첫 번째로 찾는 경로를 반환하는 방식으로 개선했습니다.

이러한 방식으로 문제를 해결하면, 코드의 가독성과 효율성이 개선되며, 불필요한 연산을 줄일 수 있습니다. DFS를 활용한 문제 풀이 시, 탐색 순서를 정렬하여 문제를 최적화할 수 있는지 고려하는 것이 중요합니다.