[프로그래머스] [Level3] 여행경로 JAVA

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

코딩테스트 연습 - 여행경로

[문제]

[풀이]

그래프 탐색문제이다.
처음엔 TreeMap과 같이 티켓과 정보를 한번에 저장해서 하려했으나 , 
키중복에서 꼬이거나 다중 Map을 써야하는 상황이 나오는 등 쉽지 않았기때문에
티켓자체를 방문지점으로 써버렷다. 그래서 티켓의 사용여부를 boolean 타입의 visit 배열로 사용했고
그냥 완전탐색 + 백트래킹으로 탐색을하다가 티켓을 전부 사용 했을 경우에
그 경로를 리스트에 넣었는데 , 이때 우선순위 큐를 썼다. 

문제의 조건에서 경로가 여러개일경우 알파벳 순으로 탐색하라는 조건이 있었기 때문에 
크기가 1인 우선순위큐를 쓰면 알파벳 순서로 정렬된 경로가 하나만 나온다.

이 경로를 잘라서 반환하면 끝.

 

import java.util.*;
import java.io.*;
 
class Solution {
    boolean[] visit;
    ArrayList<String> path = new ArrayList<>();
    PriorityQueue<String> ans = new PriorityQueue<>(1);
 
    public String[] solution(String[][] tickets) {
        visit = new boolean[tickets.length];
        dfs("ICN",0,tickets);
        return ans.poll().split(" ");
    }
 
    private void dfs(String cur,int depth,String[][] tickets) {
        path.add(cur);
        if(depth==tickets.length){
            ans.add(String.join(" ", path));
            return;
        }
        for(int i=0;i<tickets.length;i++){
            if(tickets[i][0].equals(cur) && !visit[i]) {// i번째 티켓을 쓰지 않았고 , 출발지가 같은 티켓이 있다면
                visit[i]=true;
                dfs(tickets[i][1],depth+1,tickets);
                visit[i]=false;
                path.remove(path.size()-1);
            }
        }
    }
}