깊이/너비 우선 탐색(DFS/BFS) - 여행경로

 

이 문제는 ICN 공항부터 시작하여 모든 티켓을 사용해 모든 공항을 방문하는 방법을 찾는 문제이다. 단 방문하는 경로가 여러개 생길 경우, 시작 공항을 제외하고 알파벳이 빠른 공항 순서대로 방문하도록 하여야 한다. 그렇다면 DFS 와 BFS 둘 중 어떤게 좋을지 생각을 해야한다. 위에서 말한거 처럼 방문 경로가 여러 개 일경우 시작 공항을 제외하고 알파벳이 빠른 공항 순서대로 해야하기 때문에 Stack 인 DFS가 가장 좋을 꺼 같다.

import java.util.*;

public class Solution {
    public String[] solution(String[][] tickets) {
        // 그래프 생성
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (String[] ticket : tickets) {
            graph.putIfAbsent(ticket[0], new PriorityQueue<>());
            graph.get(ticket[0]).add(ticket[1]);
        }
        
        // 결과 경로를 저장할 리스트
        List<String> path = new ArrayList<>();
        
        // "ICN"에서 DFS 시작
        dfs("ICN", graph, path);
        
        // 리스트를 배열로 변환하여 반환
        return path.toArray(new String[0]);
    }
    
    private void dfs(String airport, Map<String, PriorityQueue<String>> graph, List<String> path) {
        // 현재 공항의 인접 공항을 가져옴
        PriorityQueue<String> nextAirports = graph.get(airport);
        while (nextAirports != null && !nextAirports.isEmpty()) {
            // 다음 공항 선택
            String nextAirport = nextAirports.poll();
            // 재귀적으로 DFS 호출
            dfs(nextAirport, graph, path);
        }
        // 현재 공항을 경로에 추가 (모든 인접 공항 처리가 끝난 후)
        path.add(0, airport);
    }
}

 

문제 풀이

1. 주어진 항공권 리스트에서 각 항공권은 [출발 공항, 도착 공항]의 형태이다.

2. 여러 경로가 가능한 경우, 알파벳 순서가 앞서는 경로를 방문하기 위해 각 공항의 인접 리스트를 정렬 해야한다.

3. 모든 항공권을 사용하여 가능한 모든 경로를 탐색한다. 필요에 따라 다른 경로를 시도 해야한다.

 

 

 

Script

이 문제에서 해야 할것은 내가 방문한 항공인지 아닌지를 파악을 해야한다. putIfAbsent 를 사용하여 key 와 value를 Map에 저장하고 key 값이 존재하는 경우 Map의 value 값을 반환해주는 방식이다.  그리고 시작 공항을 제외하고 알파벳이 빠른 순서대로 방문하도록 해야한다. 레벨3 같은 경우는 내가 모르는 함수들을 사용해서 문제를 풀어야 쉽게 풀수가 있다. 자바에 어떤 함수가 있고 또 그 함수를 사용했을때의 장점과 단점에 대해서 공부하고 그 단점에 대체할수 있는 함수가 있는지 파악하는 것이 가장 중요한거 같다.