프로그래머스 여행경로 Java

🍭 필요한 로직 

모든 티켓을 다 사용해야 한다 -> DFS

갈 수 있는 경로가 여러가지라면 알파벳 순으로 -> 우선순위 큐에 넣기(자동으로 정렬이 된다) / 백트래킹으로 가능한 경우의 수 탐색

티켓을 다 사용했다면 경로를 기록하기 -> 문자열 형태로 경로 저장해놨다가 꺼내는 방식을 씀

-> String path에 공백 간격을 두고 저장, 나중에 queue.poll().split(" ")로 answer 배열에 저장하면 된다.

-> 우선순위 큐에서 알아서 알파벳 순서가 가장 빠른걸로 정렬해준다

 

 

🍭코드 

import java.util.*;
class Solution {
    public PriorityQueue <String> queue;
    public boolean[] visited;
    public String[] solution(String[][] tickets) {
        queue = new PriorityQueue<>();
        visited = new boolean[tickets.length];
        DFS(0, "ICN", "ICN", tickets);
        String[] answer = queue.poll().split(" ");
        return answer;
    }
    
    // 지금 있는 위치, 현재 몇개의 티켓을 사용했는지, 현재까지의 경로(문자열로 표기 가능)
    public void DFS(int used, String now, String path, String[][] tickets) {
        if (used == tickets.length) {
            queue.add(path);
            return;
        }
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(now)) {
                visited[i] = true;
                DFS(used+1, tickets[i][1], path + " " + tickets[i][1], tickets);
                visited[i] = false;
            }
        }
    }
}