[프로그래머스][JAVA] 43164. 여행경로

Algorithm/코딩테스트

[프로그래머스][JAVA] 43164. 여행경로

ioh'sDeveloper 2024. 6. 9. 21:45

💡 문제
여행경로(https://school.programmers.co.kr/learn/courses/30/lessons/43164)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

1. 그래프 이론

그래프: 정점과 간선으로 이루어진 자료구조. 문제에서 공항을 정점, 항공권을 간선으로 볼 수 있습니다.
인접 리스트: 각 정점에 대해 인접한 정점들을 리스트로 표현한 자료구조. 이 문제에서는 공항별로 도착 공항 리스트를 관리하기 위해 사용됩니다.

2. 탐색 알고리즘

깊이 우선 탐색 (DFS (Depth-First Search)):
- 한 정점에서 시작하여 한 방향으로 갈 수 있는 모든 경로를 탐색한 후, 더 이상 갈 곳이 없으면 뒤로 돌아와 다른 경로를 탐색하는 방식. 재귀 호출을 통해 구현됩니다.
- 깊이 우선 탐색(DFS)은 한 경로를 완전히 탐색하고 더 이상 갈 수 없으면 되돌아와 다른 경로를 탐색하는 방식의 알고리즘입니다. 재귀 호출을 통해 구현되는 경우가 많습니다. 이 문제에서는 경로를 탐색하면서 가능한 모든 경로를 시도해보고 유효한 경로를 찾는 데 사용됩니다.
백트래킹 (Backtracking):
- DFS의 일종으로, 가능한 모든 경로를 탐색하면서 조건에 맞지 않는 경로는 되돌아가는 방식. 이 문제에서는 경로의 유효성을 실시간으로 검증하면서 탐색합니다.
- 백트래킹은 DFS의 일종으로, 조건에 맞지 않는 경로는 되돌아가서 다른 경로를 시도하는 방식입니다. 유효한 경로를 찾기 위해 모든 경로를 탐색하면서 조건을 만족하지 않는 경우에는 되돌아가서 다른 경로를 시도합니다

3. 자료구조

스택: DFS 구현 시 사용될 수 있는 자료구조. 재귀 호출 자체가 시스템 스택을 이용하기 때문에 명시적으로 사용할 필요는 없습니다.
큐: BFS(너비 우선 탐색)에서 사용되지만, 이 문제에서는 사용되지 않습니다.
Map (HashMap)
- 용도: 항공권 정보를 그래프로 표현하기 위해 사용됩니다. 각 출발 공항을 키로, 도착 공항들의 리스트를 값으로 저장합니다.
- 내장 함수:
  - computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction): 키가 존재하지 않으면 주어진 매핑 함수를 이용해 값을 계산하고 추가합니다.
  - get(Object key): 주어진 키에 대응되는 값을 반환합니다.
  - keySet(): 맵의 모든 키를 반환합니다.
List (ArrayList, LinkedList)
- 용도: 경로와 도착 공항들을 저장하기 위해 사용됩니다. ArrayList는 도착 공항들을 정렬하고 관리하는 데, LinkedList는 경로를 저장하고 조작하는 데 사용됩니다.
- 내장 함수:
  - add(E e): 리스트의 끝에 요소를 추가합니다.
  - remove(int index): 지정된 인덱스에 있는 요소를 제거합니다.
  - size(): 리스트의 크기를 반환합니다.
  - sort(Comparator<? super E> c): 리스트를 주어진 비교자로 정렬합니다.

4. 정렬

알파벳 순 정렬: 주어진 항공권의 목적지를 알파벳 순으로 정렬하여, 여러 경로가 있을 때 사전 순으로 경로를 선택할 수 있게 합니다.

5. 재귀 호출

재귀 호출: 함수가 자기 자신을 호출하는 방식. DFS와 백트래킹 구현 시 사용됩니다.
재귀 탈출 조건: 재귀 호출이 무한히 반복되지 않도록 탈출 조건을 명확히 정의해야 합니다.

6. 문제 해결 과정

문제 분석: 주어진 항공권 정보를 바탕으로 그래프를 구성하고, 가능한 모든 경로를 탐색해야 한다는 것을 이해합니다.
그래프 구성: 항공권 정보를 인접 리스트 형태의 그래프로 변환합니다.
경로 탐색: DFS와 백트래킹을 사용하여 모든 경로를 탐색하고, 조건에 맞는 경로를 찾습니다.

🤓 문제 풀이

🔨 문제 설명

주어진 항공권을 모두 이용하여 여행 경로를 짜는 문제입니다. 항상 "ICN" 공항에서 출발하며, 가능한 모든 경로 중 알파벳 순서가 앞서는 경로를 찾아야 합니다.

🔨 접근 방법

그래프 구성: 각 항공권을 이용하여 출발 공항에서 도착 공항으로의 연결을 그래프로 표현합니다.
정렬: 가능한 경로가 여러 개일 경우 알파벳 순서가 앞서는 경로를 선택해야 하므로, 각 출발지에서 도착지 목록을 알파벳 순으로 정렬합니다.
DFS 탐색: "ICN"에서 출발하여 DFS를 통해 모든 경로를 탐색합니다. 경로를 탐색하며 항공권을 사용하고, 경로가 완성되지 않으면 사용했던 항공권을 되돌리는 백트래킹을 수행합니다.

🔨 문제 풀이 과정

🔨 (DFS) 자료구조 최적화 선택

이 문제에서는 DFS를 사용하는 것이 적합합니다. 이유는 모든 항공권을 사용하여 하나의 유효한 경로를 찾기 위해 백트래킹을 효율적으로 수행할 수 있기 때문입니다. 우선순위 큐를 사용하여 알파벳 순서대로 도착지를 관리하는 것도 중요한 부분입니다.

모든 경로 탐색: 모든 항공권을 사용하여 가능한 경로를 찾는 문제이므로, 모든 경로를 탐색하는 깊이 우선 탐색(DFS)이 적합합니다.
백트래킹: DFS를 통해 경로를 탐색하면서 조건에 맞지 않는 경로는 되돌아가 다른 경로를 탐색하는 백트래킹을 활용합니다.
우선순위 큐 사용: 각 출발지에서 가능한 도착지를 알파벳 순서로 정렬하여 탐색의 우선순위를 조정합니다.

🔨 (백트래킹) 선택

다른 알고리즘으로 이 문제를 해결할 수 있는 방법 중 하나는 백트래킹(Backtracking)입니다. 백트래킹은 DFS의 일종으로, 가능한 모든 경로를 탐색하면서 조건에 맞지 않는 경로는 되돌아가 다른 경로를 탐색하는 방식입니다. 이 문제에서는 가능한 경로를 탐색하다가 경로가 완성되지 않으면 되돌아가서 다른 경로를 탐색하는 방식으로 접근할 수 있습니다.

모든 경로 탐색: 백트래킹은 모든 가능한 경로를 탐색하는데 적합합니다. 문제에서 주어진 모든 항공권을 사용해야 하기 때문에 모든 경로를 탐색하는 방식이 필요합니다.
경로의 유효성 검사: 백트래킹을 사용하면 경로의 유효성을 실시간으로 검사하면서 탐색할 수 있습니다. 조건에 맞지 않는 경로는 즉시 되돌아가 다른 경로를 시도할 수 있습니다.
알파벳 순서 우선 탐색: 가능한 경로가 여러 개일 경우 알파벳 순서가 앞서는 경로를 선택해야 하므로, 백트래킹 탐색 시 도착지를 정렬하여 우선 탐색합니다.

🔨 구현코드

1) DFS를 사용한 구현코드

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        List<String> answer = new ArrayList<>();  // 경로를 저장할 리스트
        Map<String, PriorityQueue<String>> graph = new HashMap<>();  // 그래프를 표현할 맵
        
        // 그래프 구성: 각 출발지에서 도착지를 우선순위 큐로 관리
        for (String[] ticket : tickets) {
            graph.computeIfAbsent(ticket[0], k -> new PriorityQueue<>()).offer(ticket[1]);
        }
        
        // DFS 탐색 시작
        dfs("ICN", graph, answer);
        
        // 리스트를 배열로 변환하여 반환
        return answer.toArray(new String[0]);
    }
    
    private void dfs(String airport, Map<String, PriorityQueue<String>> graph, List<String> route) {
        PriorityQueue<String> destinations = graph.get(airport);  // 현재 공항에서 출발하는 도착지들
        
        // 더 방문할 곳이 있는 동안 계속 탐색
        while (destinations != null && !destinations.isEmpty()) {
            dfs(destinations.poll(), graph, route);  // 다음 도착지로 이동
        }
        
        // 경로에 현재 공항 추가 (후위 순회)
        route.add(0, airport);
    }
}

2) 백트래킹을 사용한 구현코드

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        List<String> answer = new ArrayList<>();  // 경로를 저장할 리스트
        Map<String, List<String>> graph = new HashMap<>();  // 그래프를 표현할 맵

        // 그래프 구성: 각 출발지에서 도착지를 리스트로 관리
        for (String[] ticket : tickets) {
            graph.computeIfAbsent(ticket[0], k -> new ArrayList<>()).add(ticket[1]);
        }
        
        // 각 출발지의 도착지 리스트를 알파벳 순으로 정렬
        for (String key : graph.keySet()) {
            Collections.sort(graph.get(key));
        }

        // 방문 경로 리스트
        List<String> route = new LinkedList<>();
        route.add("ICN");  // 출발점은 항상 "ICN"
        
        // 백트래킹 시작
        backtrack("ICN", graph, route, tickets.length + 1, answer);
        
        // 결과 반환
        return answer.toArray(new String[0]);
    }
    
    private boolean backtrack(String airport, Map<String, List<String>> graph, List<String> route, int targetLength, List<String> answer) {
        if (route.size() == targetLength) {
            answer.addAll(new ArrayList<>(route));
            return true;
        }
        
        // 현재 공항에서 출발하는 도착지들
        List<String> destinations = graph.get(airport);
        if (destinations == null) return false;
        
        for (int i = 0; i < destinations.size(); i++) {
            String next = destinations.remove(i);
            route.add(next);
            
            if (backtrack(next, graph, route, targetLength, answer)) {
                return true;
            }
            
            // 백트래킹: 되돌아가서 경로와 그래프 복구
            route.remove(route.size() - 1);
            destinations.add(i, next);
        }
        
        return false;
    }
}

📚 풀이 보완

코드 설명

DFS 코드 설명

그래프 구성:
- Map<String, PriorityQueue<String>> graph를 사용하여 각 출발 공항에서 도착 공항들을 우선순위 큐로 관리합니다. 우선순위 큐를 사용하면 알파벳 순서로 자동 정렬됩니다.
- graph는 Map<String, PriorityQueue<String>> 형태로 각 출발 공항에서 도착 공항들을 우선순위 큐로 관리합니다. 우선순위 큐를 사용하여 도착지를 자동으로 알파벳 순으로 정렬합니다.
- 각 항공권을 순회하며 graph를 구성합니다.
DFS 탐색:
- 재귀함수 dfs를 사용하여 현재 공항에서 출발하는 모든 경로를 탐색합니다. 우선순위 큐에서 도착지를 하나씩 꺼내어 다음 도착지로 이동합니다.
- dfs 메서드를 정의하여 재귀적으로 경로를 탐색합니다.
- 현재 공항에서 출발하는 모든 도착지를 우선순위 큐에서 하나씩 꺼내어 다음 도착지로 이동합니다.
- 더 이상 방문할 도착지가 없을 때 현재 공항을 경로에 추가합니다.
경로 추가:
- 후위 순회 방식으로 경로를 추가합니다. 즉, 더 이상 이동할 도착지가 없을 때 현재 공항을 경로에 추가합니다.
- 후위 순회 방식으로 경로를 추가하여 모든 경로가 완성된 후 경로를 완성합니다.

BFS와 DFS 비교

DFS 장점: 깊이 우선 탐색을 통해 모든 경로를 탐색하고, 백트래킹을 통해 모든 항공권을 사용한 경로를 찾아낼 수 있습니다.
BFS의 경우: 너비 우선 탐색은 최단 경로를 찾는 데 유리하지만, 이 문제에서는 모든 항공권을 사용해야 하므로, 깊이 우선 탐색이 더 적합합니다.

백트래킹 코드설명

그래프 구성:
- graph는 Map<String, List<String>> 형태로 각 출발 공항에서 도착 공항들을 리스트로 관리합니다.
- 각 항공권을 순회하며 graph를 구성합니다.
- 각 출발지의 도착지 리스트를 알파벳 순으로 정렬합니다.
백트래킹 탐색:
- backtrack 메서드를 정의하여 재귀적으로 경로를 탐색합니다.
- 현재 공항에서 출발하는 모든 도착지를 순회하며 다음 도착지로 이동합니다.
- 더 이상 방문할 도착지가 없을 때 경로를 완성합니다.
- 백트래킹 시 경로와 그래프를 복구하여 다른 경로를 탐색합니다.

📍 Plus+

시간 복잡도 분석

그래프 구성: O(E log E) (E는 항공권의 수)
- 각 항공권을 우선순위 큐에 삽입하는 데 log E의 시간이 걸립니다.
DFS 탐색: O(V + E)
- 각 공항(V)과 항공권(E)을 방문하는 데 걸리는 시간입니다.
최종 시간 복잡도: O(E log E + V + E)

공간 복잡도 분석

그래프 저장 공간: O(V + E)
- V는 공항의 수, E는 항공권의 수
경로 저장 공간: O(V)
최종 공간 복잡도: O(V + E)

요약

시간 복잡도: O(E log E + V + E) (항공권의 수와 공항의 수에 비례)
공간 복잡도: O(V + E) (그래프와 경로 저장 공간)

DFS와 백트래킹을 사용한 문제 풀이의 차이점과 각 알고리즘의 장단점

DFS (깊이 우선 탐색)

알고리즘 설명:
- DFS는 특정 경로를 끝까지 탐색한 후, 다른 경로로 이동하는 방식입니다. 주어진 문제에서는 모든 항공권을 사용하여 가능한 경로를 모두 탐색하고 유효한 경로를 찾기 위해 DFS를 사용합니다.
장점:
- 구현이 간단하고 직관적입니다.
- 모든 가능한 경로를 탐색하므로, 정답을 반드시 찾을 수 있습니다.
단점:
- 경우의 수가 많을 때 시간 복잡도가 높아질 수 있습니다.
- 경로의 유효성을 매번 검증하지 않으면 불필요한 경로까지 탐색하게 됩니다.

백트래킹

알고리즘 설명:
- 백트래킹은 DFS의 일종으로, 가능한 모든 경로를 탐색하면서 조건에 맞지 않는 경로는 되돌아가 다른 경로를 탐색합니다. 이 문제에서는 가능한 경로를 탐색하다가 경로가 완성되지 않으면 되돌아가서 다른 경로를 탐색합니다.
장점:
- 조건에 맞지 않는 경로는 빠르게 되돌아가므로, 탐색을 효율적으로 수행할 수 있습니다.
- 경로의 유효성을 실시간으로 검사하면서 탐색합니다.
단점:
- 구현이 상대적으로 복잡할 수 있습니다.
- 경우에 따라서는 DFS와 비슷한 시간 복잡도를 가질 수 있습니다.

시간 복잡도

DFS:시간 복잡도는 모든 경로를 탐색하므로 O(N!)이 될 수 있습니다. 여기서 N은 항공권의 수입니다. 최악의 경우 모든 경로를 시도해야 하므로, 매우 큰 시간이 소요될 수 있습니다.
백트래킹:시간 복잡도는 최악의 경우 DFS와 유사하게 O(N!)이 될 수 있습니다. 하지만, 조건에 맞지 않는 경로를 빠르게 배제할 수 있어 실질적인 탐색 시간은 DFS보다 효율적일 수 있습니다.

공간 복잡도

DFS:재귀 호출에 의해 사용되는 스택 공간이 필요합니다. 최대 깊이는 N이므로, 공간 복잡도는 O(N)입니다.
백트래킹:재귀 호출과 경로를 저장하기 위한 공간이 필요합니다. 최대 깊이는 N이므로, 공간 복잡도는 O(N)입니다.

요약

DFS와 백트래킹 모두 깊이 우선 탐색을 사용하여 가능한 모든 경로를 탐색합니다.
DFS는 구현이 간단하고 직관적이지만, 조건에 맞지 않는 경로까지 탐색하여 비효율적일 수 있습니다.
백트래킹은 조건에 맞지 않는 경로를 빠르게 배제하여 효율적으로 탐색할 수 있습니다.
두 알고리즘 모두 최악의 경우 시간 복잡도는 O(N!)이지만, 백트래킹이 실질적인 탐색 시간은 더 효율적일 수 있습니다.
공간 복잡도는 둘 다 O(N)입니다.

차이점과 장단점 요약

DFS는 단순하고 직관적이지만, 비효율적인 경로까지 탐색할 수 있습니다.
백트래킹은 조건에 맞지 않는 경로를 빠르게 배제하여 더 효율적입니다.
두 알고리즘 모두 시간 복잡도는 최악의 경우 O(N!)이지만, 백트래킹이 실질적으로 더 효율적입니다.
공간 복잡도는 둘 다 O(N)입니다.

'Algorithm > 코딩테스트' 카테고리의 다른 글

[프로그래머스][JAVA] 43163. 단어변환 (1)	2024.06.09
[프로그래머스][JAVA] 87694. 아이템 줍기 (1)	2024.06.09
[프로그래머스][JAVA] 84512. 모음사전 (0)	2024.06.05
[프로그래머스][JAVA] 84021. 퍼즐조각채우기 (0)	2024.06.01
[프로그래머스][JAVA] 86971. 전력망을 둘로 나누기 (0)	2024.06.01

현재글[프로그래머스][JAVA] 43164. 여행경로

ioh's Development

Back-End 주니어 개발자 입니다. 개발이 재밌는 사람입니다만... :D

개발자수학, 항해, 자료구조, 알고리즘, til, 99일지, 디스크컨트롤러, 개발자스터디, 코딩테스트, 정렬된큐, 99클럽, heap, 수학리부트, BFS, dfs, 프로그래머를위한기초수학, java, Queue, 정렬, 프로그래머스,

Today :
Yesterday :

일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

ioh's Development