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

문제

---

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

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

생각하기

---

백트래킹의 기초를 알 수 있는 문제였다.
DFS를 통해서 백트래킹을 구현할 수 있다.

동작

        // tickests (문자형)2차원 배열 정렬
        Tickets.sortWith{x,y->
                if(x[0].equals(y[0])) {
                    x[1].compareTo(y[1])
                }
                else x[0].compareTo(y[0])
        }

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

        for(i in 0..len-1) {
            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)를 사용해서 마지막 결과값을 정리해서도 충분히 답을 찾을 수 있다.

코드

---

Kotlin

import java.util.*;

class Solution {

    private lateinit var Tickets : Array<Array<String>>
    private lateinit var visit : Array<Boolean>
    private var len : Int = 0;
    private var list : MutableList<String> = ArrayList<String>();
    private var sb = StringBuilder();


    fun solution(tickets: Array<Array<String>>): Array<String> {
        Tickets = tickets;
        len = tickets.size;
        visit = Array<Boolean>(len, {false});

        // tickests (문자형)2차원 배열 정렬
        Tickets.sortWith{x,y->
                if(x[0].equals(y[0])) {
                    x[1].compareTo(y[1])
                }
                else x[0].compareTo(y[0])
        }


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

        var result = list.get(0);
        var st = StringTokenizer(result);
        var answer = Array<String>(len+1, {""});
        for(i in 0..len) {
            answer[i] = st.nextToken();
        }

        return answer
    } // End of solution

    private fun DFS( boarding : String, route : String, depth : Int) {
        sb = StringBuilder();

        if(depth == len) {
            list.add( route )
            return;
        }

        for(i in 0..len-1) {
            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