[Java] 여행경로 (프로그래머스)

정상준·2022년 12월 27일

프로그래머스

목록 보기

2/4

📍 출처

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43164

📝 문제

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

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

📍 제한

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

⌨️ 예제 입력

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]

🖨 예제 출력

["ICN", "JFK", "HND", "IAD"]

📚 내가 제출한 코드

import java.util.*;
import java.io.IOException;

class Solution {
	// 방문 확인
    boolean visited[];
    // 갈 수 있는 모든 경로 저장
    ArrayList<String> allRoute;

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        visited = new boolean[tickets.length];
        allRoute = new ArrayList<>();

        int count = 0;
        
        dfs(count,"ICN", "ICN", tickets);
        // 갈 수 있는 모든 경우의 수 오름차순 정렬
        Collections.sort(allRoute);
		// 정렬했으므로 맨 앞에 있는게 알파벳순서가 가장 빠르므로 첫 번째거 가져옴
        answer = allRoute.get(0).split(" ");
        return answer;
    }
    //갈 수 있는 모든 곳 순회
     public void dfs(int cnt, String start, String route, String[][] tickets) {
     	// 끝까지 순회했으면
         if (cnt == tickets.length) {
         // allRoute에 저장
            allRoute.add(route);
            return;
        }

     for (int i = 0; i < tickets.length; i++) {
     		//방문하지 않았고 전에 받은 start와 tickets에 있는 출발지가 같으면
            if (!visited[i] && start.equals(tickets[i][0])) {
                visited[i] = true;
                dfs(cnt + 1, tickets[i][1], route + " " + tickets[i][1], tickets);
                // 모든 경우에 수 돌아야하니 다시 false로 변경
                visited[i] = false;
            }
        }
    }
}