프로그래머스 3단계 여행경로 [java]

문제 설명

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 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]
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]	[ICN, ATL, ICN, SFO, ATL, SFO]

 

해결방안

 

처음에 문제를 풀때 가능한 경로가 2개 이상일 경우가 조금 어려웠다. 결국 검색을 해봤고 생각을 바꿔서 문자열 리스트를 만들고 오름차순으로 바꾸고 맨 앞에 문자열을 구하면 되는것으로 생각을 바꾸게 되었다. 그 외에는 시작점과 끝점, 그리고 문자열 만큼의 boolean배열을 이용해 dfs를 구현하면 된다.

 

dfs메소드

- tickets과 시작을 가리키는 문자열, 현재 진행된 경로, 개수를 매개변수로 가져가면 된다.

개수는 지나온 경로를 가리키므로 개수가 ticket의 개수와 같아지면 문자열리스트 전역변수에 현재 경로를 추가한다.

그렇지 않고 방문하지 않았는데 tickets의 0번째가 시작을 가리키는 문자열과 같으면 방문한 걸로 바꿔주고 dfs를 다시 호출한다. 여기서 count의 개수는 1 증가시키고 시작점은 tickets의 원소의 1번째로 바꾼다. 현재 경로를 나타내는 문자열에도 마찬가지로 tickets의 원소의 1번째를 더해준다.

 

dfs메소드가 끝나고 다시 solution으로 돌아오면 경로들이 저장된 전역변수 paths를 오름차순으로 바꿔주고 가장 앞에 있는 원소를 answer에 넣어서 리턴하면 된다.

 

코드

 

package programmers_3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class travel_route {
    public static void main(String[] args) {
        String[][] tickets = {{"ICN","SFO"},{"ICN","ATL"}
        ,{"SFO","ATL"},{"ATL","ICN"},{"ATL","SFO"}};
        travel_route s = new travel_route();
        System.out.println(Arrays.toString(s.solution(tickets)));
    }
    boolean[] visit;
    ArrayList<String> paths = new ArrayList<>();
    public String[] solution(String[][] tickets){
        visit = new boolean[tickets.length];
        String[] answer = {};
        dfs(tickets,"ICN","ICN",0);
        Collections.sort(paths);
        answer = paths.get(0).split(" ");
        return answer;
    }

    public void dfs(String[][] tickets,String start,String path,int count){
        if(tickets.length == count){
            paths.add(path);
            return;
        }
        for(int i = 0; i< tickets.length;i++){
            if(!visit[i] && tickets[i][0].equals(start)){
                visit[i] = true;
                dfs(tickets,tickets[i][1],path + " " + tickets[i][1],count+1);
                visit[i] = false;
            }
        }
    }
}