[PGS] 프로그래머스 - 여행경로 (JAVA)

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

프로그래머스

 

import java.util.*;

class Solution {
    static int[] visited;
    static PriorityQueue<String> pq;
    
    public void dfs(String cityName, String[][] tickets, String path, int node){
        if(node==tickets.length){
            //다 돌았다
            pq.add(path);
            return;
        }
        for(int i=0;i<tickets.length;i++){
            if(visited[i]==0 && cityName.equals(tickets[i][0])){
                visited[i] = 1; //방문
                dfs(tickets[i][1],tickets,path+","+tickets[i][1],node+1);
                visited[i] = 0; //백트래킹
            }
        }
        
    }
    public String[] solution(String[][] tickets) {
        visited = new int[tickets.length];
        pq = new PriorityQueue<>();
        
        dfs("ICN",tickets,"ICN",0);
        String tmp = pq.poll();
        String[] answer = {};
        
        answer = tmp.split(",");
        
        return answer;
    }
}

 

방문여부 확인하는 것을 잊지 말자 !!