여행경로 [프로그래머스]

지니🧸·2024년 4월 10일

알고리즘

목록 보기

21/43

문제

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제약 사항

모든 공항은 알파벳 대문자 3글자로 이루어집니다.

주어진 공항 수는 3개 이상 10,000개 이하입니다.

tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.

주어진 항공권은 모두 사용해야 합니다.

만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예제

풀이

DFS + 백트래킹의 혼합인 문제다.

DFS로 탐색했을 때 가능한 경로가 2개 이상이면 알파벳 순서로 빠른 것을 반환해야 하기 때문에 가능한 경로를 모두 저장해 탐색이 끝나면 정렬해서 첫번째 경로를 반환하고자 한다.

탐색 과정

무조건 "ICN"에서 시작한다. (route도 "ICN"으로 시작한다)
현재 공항에서 이동 가능한, 아직 방문하지 않은 공항을 모두 탐색한다.
2-1. 그 공항은 방문한 것으로 처리하고,
2-2. 그 공항을 경로에 더해 DFS를 재귀호출한다

백트랙킹

DFS 재귀호출이 끝나는 경우는 두 가지 경우인데

더 이상 현재 공항에서 갈 공항이 없다
또는, 경로가 완성됐다

1의 경우는 백트랙킹으로 해결한다.
공항 A에서 갈 수 있는 공항이 공항 B와 공항 C라 했을 때, 공항 B에서 탐색이 실패하면 공항 B에서부터 탐색했던 공항들을 모두 방문취소 처리하고, 공항 C에서 탐색을 다시 시작한다.

2의 경우는 현재까지의 경로가 모든 티켓을 다 사용하는지 확인하고, 그럴 경우 이 경로의 탐색을 끝낸다. 하지만 여기서 탐색이 완전히 끝나는 것이 아니라, 다른 가능한 경로를 방문한다.

코드

import java.util.*;

class Solution {
    List<String> routes; 
    int[] visited;
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        int visitedAirports = 0;
        routes = new ArrayList<>();
        visited = new int[tickets.length];
        
        dfs("ICN", "ICN", tickets, visitedAirports);
        
        Collections.sort(routes);
        answer = routes.get(0).split(" ");
        
        return answer;
    }
    
    public void dfs(String start, String route, String[][] tickets, int visitedAirports){
        if (visitedAirports == tickets.length){
            routes.add(route);
            return;
        }
        
        for(int i = 0; i < tickets.length; i++){
            if(start.equals(tickets[i][0]) && visited[i] == 0){
                visited[i] = 1;
                dfs(tickets[i][1], route + " " + tickets[i][1], tickets, visitedAirports + 1);
                visited[i] = 0;
            }
        }
    }
    
}