프로그래머스 여행경로
https://programmers.co.kr/learn/courses/30/lessons/43164?language=java

문제

---

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

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

생각하기

---

DFS 백트래킹을 통해서 푸는 문제이다.

유의할 점은 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return한다.

가 주의 할 점이었다.

동작

    	// tickets 정렬 (람다식 정렬)
    	Arrays.sort(tickets, (o1, o2) -> {
    		if(o1[0].equals(o2[0])) {
    			return o1[1].compareTo(o2[1]);
    		}
    		else {
    			return o1[0].compareTo(o2[0]);
    		}
    	});

위에서 말한 알파벳 순서가 앞서는 경로를 선택하기 위해서 tickets 2차원 배열의 정렬을 먼저 시작한 후 DFS를 실행했다. 정렬은 Array.sort에서 compareTo를 사용하여 문자열을 비교하여 정렬하였다.

    	for(int i=0; i<len; i++) {

    		if(visit[i]) continue;

    		if( tickets[i][0].equals(boarding) ) {
    			visit[i] = true;
    			sb.append(route).append(' ').append(tickets[i][1]);
    			DFS(tickets[i][1], sb.toString() , depth + 1);
    			visit[i] = false;
    		}
    	}

이 문제의 핵심은 tickets를 탐색하면서, 각 공항들을 방문하는 순서대로 공항의 이름을 list에 넣는 것이 아닌, 방문한 순서전체를 문자열로 만들어서 방문순서가 통으로 list하나에 들어가는 것이다.

처음 내가 생각한 결과 값은 아래와 같다
list.get(0) "ICN"
list.get(1) "ATL"
list.get(2) "ICN"
...

위 같은 list 의 값을 가질 줄 알았는데,

이 문제는
list.get(0) "ICN ATL ICN SFO ATL SFO"
list.get(1) "ICN SFO ATL ICN ATL SFO"
...
의 형식이였던 것이다.

대충 예시로 들어보자면, 결과 값이
["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
라고 했을 때, list에는 "ICN ATL ICN SFO ATL SFO"의 문자열 전체가 통으로 들어가는 것이다.

list(0)에는 "ICN ATL ICN SFO ATL SFO"가 들어갔고, 예시에서 ICN 출발이 2개가 있기 때문에, 다음 list에는 "ICN SFO ATL ICN ATL SFO" 해당 결과가 들어가는 것이다.

이렇게 되는 경로에서 list 첫 번째 값을 출력하는 원하는 정돈된 결과를 얻을 수 있다.

만약 내가 만든 코드처럼 위에서 2차원 배열을 미리 정리하지 않더라도
Collections.sort(list)를 사용해서 마지막 결과값을 정리해서도 충분히 답을 찾을 수 있다.

코드

---

Java

import java.util.*;

class Solution {
	static StringBuilder sb = new StringBuilder();
    static String tickets[][];
	static boolean visit[];
	static List<String> list = new ArrayList<>();
	static int len;


    public String[] solution(String[][] tickets) {
    	this.tickets = tickets;
    	len = tickets.length;
    	visit = new boolean[len];

    	// tickets 정렬 (람다식 정렬)
    	Arrays.sort(tickets, (o1, o2) -> {
    		if(o1[0].equals(o2[0])) {
    			return o1[1].compareTo(o2[1]);
    		}
    		else {
    			return o1[0].compareTo(o2[0]);
    		}
    	});

    	DFS("ICN", "ICN", 0);

    	// 결과 출력
    	String result = list.get(0);
    	StringTokenizer st = new StringTokenizer(result);
    	String answer[] = new String[len+1];

    	for(int i=0; i<len + 1; i++) {
    		answer[i] = st.nextToken();
    	}

        return answer;
    } // End of solution

    // 백트래킹 -> 재귀 탈출 조건, 백트래킹 탈출 조건 2개 필요
    private static void DFS( String boarding, String route, int depth ) {
    	sb = new StringBuilder();

    	if(depth == len) {
    		list.add(route);
    		return;
    	}
	
    	for(int i=0; i<len; i++) {

    		if(visit[i]) continue;

    		if( tickets[i][0].equals(boarding) ) {
    			visit[i] = true;
    			sb.append(route).append(' ').append(tickets[i][1]);
    			DFS(tickets[i][1], sb.toString() , depth + 1);
    			visit[i] = false;
    		}
    	}
	
    } // End of DFS

} // End of Solution class