여행경로(Java)

bearMin·2024년 5월 30일

🎯문제

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

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

제한사항

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

입출력 예

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명

예제 #1

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

예제 #2

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

✏️풀이

코드

import java.util.*;

class Solution {
	// 방문여부를 저장할 배열
    boolean[] visit;
    // 모든 경로를 저장할 배열
    ArrayList<String> allRoute;
    // dfs 탐색 메소드
    public void dfs(String start, String route, String[][] tickets, int depth) {
    	// 주어진 항공권을 모두 사용했다면
        if(depth == tickets.length) {
            allRoute.add(route);
            return;
        }
        
        for(int i = 0; i < tickets.length; i++) {
        	// 사용하지 않은 항공권이면서 시작 위치가 동일할 경우
            if(!visit[i] && start.equals(tickets[i][0])) {
                visit[i] = true;
                dfs(tickets[i][1], route + " " + tickets[i][1], tickets, depth + 1);
                visit[i] = false;
            }
        }
    }
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        visit = new boolean[tickets.length];
        allRoute = new ArrayList<>();
        
        dfs("ICN", "ICN", tickets, 0);
        
        // 저장된 모든 경로를 알파벳 순으로 정렬
        Collections.sort(allRoute);
        answer = allRoute.get(0).split(" ");
        
        return answer;
    }
}

설명

dfs 탐색 방식을 사용하여 해결하였다.

사용한 변수들이 뜻하는 것은 다음과 같다.

ArrayList allRoute
- 모든 경로를 저장할 배열
boolean[ ] visit
- 방문여부를 저장할 배열

dfs 탐색 메소드는 깊이 우선 탐색을 진행하는 메소드로 시작할 위치와, 탐색된 경로, 항공권의 정보, 깊이를 매개변수로 가진다.

만약 주어진 항공권을 모두 사용했다면 allRoute라는 배열에 탐색된 경로를 저장해주고 반환한다.

항공권을 모두 사용하지 않았다면 반복문을 통해 탐색을 진행한다. 이때 start로 넘겨주는 값은 탐색한 항공권의 도착지점이다. 여행을 진행해야하기 때문에 도착지점을 다음 탐색의 시작지점으로 잡고 탐색을 해야 경로가 완성이 되기 때문이다.

visit 배열과 allRoute 배열을 모두 생성해준 뒤에 ICN에서부터 탐색을 진행한다.

모든 탐색이 끝난 뒤 저장된 경로를 알파벳 순으로 정렬하여 가장 앞에 나오는 경로를 반환해주면 문제를 해결할 수 있다!

💡느낀 점

아직 Level2, Level3의 문제들만 풀어서 그런지 BFS, DFS 관련한 문제들이 유독 많은 것 같다. 기존에 탐색했던 항공권의 도착지점이 다음 탐색을 진행할 때 시작지점이 된다는 것만 잘 기억해서 코드를 짠다면 무리없이 해결할 수 있을 것 같다. 계속 비슷한 유형의 문제를 풀다보니 조금 더 빠르게 접근할 수 있는 것 같다. 실력이 늘고 있다는 생각이 드니까 뿌듯하다..!