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

Lv3의 DFS를 활용하는 문제입니다.

---

<문제 설명>

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 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] 가 알파벳 순으로 앞섭니다.

---

<나의 풀이>

항상 인천에서 출발하며 알파벳 순서가 빠른 경로가 우선이라는 조건이 있다.

 

처음 입력되는 tickets을 정렬하고 동일하게 ICN에서 출발하더라도 도착지가 빠른 티켓먼저 방문하면 되겠다고 생각함

그리고 모든 티켓을 방문한 후 나오는 정답의 길이는 항상 입력 티켓길이+1이라는 조건을 활용함

 

그러나 이렇게 작성할 경우 모든 경로를 방문하지 못해 무한루트에 빠지게 되는 것을 알았다ㅜㅜ

또한 알파벳 기준이 나올 수 있는 경로들 중에서 알파벳 순으로 비교를 해주면 되는 것이고

내 처음 생각대로 할 필요가 없었음!

 

테스트 케이스를 한가지 더 추가해 이 케이스를 통과할 수 있으면 되는듯!

 

[["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]]

 

정답: ["ICN", "COO", "ICN", "BOO", "DOO"]

 

틀린 코드

import java.util.*;

class Solution {
    boolean[] visited;
    ArrayList<String> route;

    public void bfs(String[][] tickets, String tmp){
        while(route.size()<tickets.length+1){
            for(int i=0; i<tickets.length; i++){
                if(tickets[i][0].equals(tmp) && !visited[i]){
                    route.add(tickets[i][1]);
                    visited[i] = true;
                    tmp = tickets[i][1];
                }
            }
        }
    }
    public String[] solution(String[][] tickets) {
        Arrays.sort(tickets, new Comparator<String[]>() {
            public int compare(String[] arr1, String[] arr2) {
                if( ((Comparable)arr1[0]).compareTo(arr2[0]) > 0 ){
                    return 1;
                }
                else if(arr1[0].equals(arr2[0])){
                    if(((Comparable)arr1[1]).compareTo(arr2[1]) > 0 ){
                        return 1;
                    }
                    else{
                        return -1;
                    }
                }
				else{
                    return -1;
                }
            }
        });
        visited = new boolean[tickets.length];
        route = new ArrayList<>();

        route.add("ICN");
        String start = "";
        for(int i=0; i<tickets.length; i++){
            if(tickets[i][0].equals("ICN")){
                route.add(tickets[i][1]);
                start = tickets[i][1];
                visited[i] = true;
                break;
            }
        }
        bfs(tickets, start);

        String[] answer = new String[tickets.length+1];
        for(int i=0; i<route.size(); i++){
            answer[i]=route.get(i);
        }
        return answer;
    }
}

수정 코드

결국 다른 분 코드를 참고했는데 가장 이해가 잘되었던 코드!

 

https://geehye.github.io/programmers-dfs-bfs-04/

import java.util.*;

class Solution {
	List<String> list = new ArrayList<>();
	static String route = "";
	static boolean[] visit;
	
	private void dfs(String[][] tickets, String end, int cnt) {
		route += end + ",";
		
		if(cnt == tickets.length) {
			list.add(route); 
            return;
		}
		
		for(int i = 0; i < tickets.length; i++) {
			String s = tickets[i][0];
            String e = tickets[i][1];
			if(s.equals(end) && !visit[i]) {
				visit[i] = true;
				dfs(tickets, e, cnt + 1);
				visit[i] = false; 
                route = route.substring(0, route.length()-4);
			}
		}
	}
	
	public String[] solution(String[][] tickets) {
		for(int i = 0; i < tickets.length; i++) {
			visit = new boolean[tickets.length];
			String start = tickets[i][0], end = tickets[i][1];
			
			if(start.equals("ICN")) {
				route = start + ","; 
                visit[i] = true; 
				dfs(tickets, end, 1);
			}
		}
		
		Collections.sort(list);
		String[] answer = list.get(0).split(",");

		return answer;
    }
}

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/43164?language=java

코딩테스트 연습 - 여행경로 | 프로그래머스