[알고리즘] 프로그래머스 여행경로 :: 우유

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

프로그래머스

문제 푸는 방식을 찾아내는 것이 핵심이었던 문제였다. 구현하는 시간보다 문제를 어떻게 풀어야될지에 대한 생각을 하는데 시간을 더 많이 소요 했던거 같다. 

이번 문제의 핵심은 백트레킹 (BackTraking) 을 사용하여 가능할 수 있는 모든 경로를 ArrayList<String> 에 저장하는 것

- 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서가는 경로를 return 해줘야 하기 때문에 Collections.sort(list)를
사용해서 ArrayList 에 추가된 String 값을 알파벳 순서로 재배열 한뒤 첫번째 인덱스에 저장된 String 값 return
- visited[i] = true 로 방문체크를 하고 DFS 함수를 빠져나오면서 다시 visited[i] = false 를 해주기 때문에 같은 출발지에서 여러 도착지로, 즉 중복된 출발지에서 도착지가 달라도 모든 경로를 탐색할 수 있게 한다.

import java.util.*;

class Solution {

    static boolean visited[];
    static ArrayList<String> list = new ArrayList<String>();

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        visited = new boolean[tickets.length+1];

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

        Collections.sort(list);

        return list.get(0).split(" ");
    }

    public void DFS(String start, String path, int depth, String tickets[][]) {
        if (depth == tickets.length){
            list.add(path);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals(start) && !visited[i]) {
                visited[i] = true;
                DFS(tickets[i][1], path + " " + tickets[i][1], depth + 1, tickets);
                visited[i] = false;
            }
        }
    }
}