(25.01.28) DFS 알고리즘의 시간 부족 Time Limit Exceeded 해결 : 자료구조의 활용

 

 

DFS의 다중 탐색을 여러번 사용하는 경우, 반복문 단위에서 DFS 횟수를 줄여서 Time Limit을 벗어날 수 있었다.(이분탐색)

 

하지만 어떤 조건에 맞춱가면서 하나의 DFS를 찾아가는 알고리즘에서 발생하는 것은 탐색해야하는 데이터에 비해, 리소스가 (메모리 등)이 한정적일 때 발생할 수도 있다.

즉, 하나의 깊이 탐색 자체가 너무 많은 리로스를 사용하기 때문인데,

이 때, List 나 Set 처럼 백트래킹이 있는 알고리즘에서 불필요한 사용이 있을 수 있다.

 

이 때,  백트래킹을 진행하지 않고 조건에 만족하는 방향만 찾아게 하면서 탐색 속도를 줄이려면 어떻게 해야할까.

---

Question

are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

import java.util.*;

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> totalPath = new ArrayList<>();
        int pathCount = tickets.size();

        // 초기 설정
        totalPath.add("JFK");

        // 행지 마다 맵 리스트 생성
        Map<String, List<String>> map = new HashMap<>();
        for(List<String> ticket : tickets) {
            String departure = ticket.get(0);
            String arrival = ticket.get(1);

            map.computeIfAbsent(departure, k -> new ArrayList<>()).add(arrival);
        }

        // 행성지 마다 리스트 재정렬
        for (String departure : map.keySet()) {
            Collections.sort(map.get(departure));
        }

        String departure = "JFK";
        List<String> visited = new ArrayList<>();

        visited.add(departure);
        dfs(map, visited, departure, pathCount);

        return visited;

    }

    public boolean dfs(Map<String, List<String>> map, List<String> visited, String departure, int pathCount) {
        // visited 의 크기가 전체 경로와 같다면
        if(visited.size() == pathCount+1) return true;

        // 출발지에 대한 행선지 리스트
        List<String> arrivalList = map.get(departure);

        // 다음 행성지에서 출발하는 티켓이 없을 경우
        if(arrivalList == null) {
           return false;
        }

        // 행선지 하나씩 방문하면서, visited 아닐경우에 바로 dfs 재귀하고 탈출
        for(int i = 0 ; i < arrivalList.size(); i++) {
            String arrival = arrivalList.get(i);

            // 초기 세팅 
            visited.add(arrival);
            arrivalList.remove(i);

            // 최종 dfs가 true 일경우에만 true
            if(dfs(map, visited, arrival, pathCount)) return true;

            // 그렇지 않을 경우 백트래킹, 복구
            visited.remove(visited.size()-1);
            arrivalList.add(i, arrival);
        }

        return false;
    }
}

문제상황

• 위의 재귀적인 DFS 구조로 순서대로 출발지 - 목적지의 나열을 정상적으로 작동하는 알고리즘을 작동시키면 특정 크기가 큰 데이터에서 Time Limit Exceeded 이 발생
• 전체 탐색을 진행하는 과정에서 시간 효율이 부족한 것으로 파악
  • DFS가 진행되어서 맨 마지막에 도달했을 때, false 를 반환 할 시에 백트래킹 진행 과정에서 문제가 발생할 가능성이 있음
    • ArrayList, LinkedList 자료구조에서 add(index, 넣을 데이터내용) 메서드를 활용해서 특정 인덱스에 자료를 넣는 과정은, 변수의 인덱스 이후의 모든 데이터를 한 인덱스씩 뒤로 미루는 탐색이 DFS 재귀를 진행할 때마다 발생
    • → 과도한 중복 탐색이 많이 발생
• 인덱스로 출발지에 해당하는 목적지를 바로 측정하기 위해서 map 자료구조를 활용했지만, 이는 크게 영향을 주지 못함
  • DFS를 여러개를 계속 중복해서 진행하면서 모든 경로를 다 통과하는 것을 찾아야 하는 방향이기 때문에 크게 영향이 없는 방안

해결방안 : PriorityQueue 활용

import java.util.*;

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> totalPath = new ArrayList<>();

        // 행지 마다 맵 리스트 생성
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for(List<String> ticket : tickets) {
            String departure = ticket.get(0);
            String arrival = ticket.get(1);

            map.computeIfAbsent(departure, k -> new PriorityQueue<>()).add(arrival);
        }

        String departure = "JFK";
        dfs(totalPath, map, departure);

        return totalPath;
    }

    public void dfs(List<String> totalPath, Map<String, PriorityQueue<String>> map, String departure) {
        // departure에 해당하는 행선지
        PriorityQueue<String> arrivalQueue = map.get(departure);

        // 다음 행성지에서 출발하는 티켓이 없을 경우 까지 진행을 함
        while(arrivalQueue != null && !arrivalQueue.isEmpty()) {
            String arrival = arrivalQueue.poll();

            dfs(totalPath, map, arrival);
        }

        // 꼬리를 물어 모두 탐색했으므로, 맨 처음의 departure 을 주입
        totalPath.add(0, departure);
    }
}

Map<String, PriorityQueue<String>> map = new HashMap<>();

• 출발지에 대한 여러 도착지를 정리하는 자료 구조를 ArrayList에서 PriorityQueue로 변경
  • 따로 Collections.sort() 하여 오름차순으로 정렬할 필요 없음
  • Priority 최우선순위(정렬순서)를 사용하기 위해 위치에 대한 정보를 담고 있기 때문에 내부 Binary Heap(이진 힙)사용하기 때문에 삽입/삭제가 매우 빠름
  • Queue 특성으로 poll 매우 용이
  • TreeSet이 아니기 때문에 중복 허용
• Queue이기 때문에 poll()을 사용해서 자료를 끄집어 내면 visited 확인할 필요없이 바로 사용할 수 있음
  • 필요없는 visited와 백트래킹을 할 필요가 없음≠

      // 다음 행성지에서 출발하는 티켓이 없을 경우 까지 진행을 함
        while(arrivalQueue != null && !arrivalQueue.isEmpty()) {
            String arrival = arrivalQueue.poll();

            dfs(totalPath, map, arrival);
        }
        ...
        totalPath.add(0, departure);

• 백트래킹을 해야하는 조건을 while.문 조건문안에 포함시켜서(다음 목적지가 등록이 안되었거나(null) 모두 사용했을때(empty)를 피해서 재귀로 끝까지 진행
• → 그 상태에서 맨 앞에 최우선순위(0-index)에 출발지를 계속 넣으면서 줄줄이 위로 올라오면서 totalPath 전체 경로 완성

정리

• 특정 조건에서 하나의 DFS 를 찾아가는 것이 아니라, 여러가지 DFS 조건중에서 가장 이상적인 것을 찾아가는 경우(Target 이 없는 경우), Queue와 while문 사용하는 BFS 구조를 활용해서 조건을 만족 시키는 DFS만 진행할 수 있도록 해야함
  • 저번의 물을 채워서 확인하는 DFS 일경우엔 위와 아래 시작 도착이 명확하고 도착하는 경우가 있는지 직접적으로 DFS 자체를 반복하는 것이기 때문에 Queue 사용이 효율적이니 않을 수 있음
• 모든 DFS 구조가 visited를 기반으로 반복문으로 진행할 필요는 없다는 것

---

Queue 자료구조는 BFS에서 많이 사용해서 친숙하지만, 캐싱 작업에서 검색 순위를 구현하는 등의 PriorityQueue를 활용해서 알고리즘을 작성하면 코드 양과 알고리즘이 효율적으로 시간 제한없이 잘 정리될 수 있다.

TreeSet 구조와 같이 순서, 순위를 부가적으로 기억하고 있는 이 PriorityQueue 자료구로즐 적극적으로 활용할 수 있어야 효율적인 코드를 작성할 수 있을 것이다.