프로그래머스 - 여행경로/DFS/BFS JAVA 자바

처음에는 되게 쉽다고 생각했는데

실행시키니까 기본테케는 작동하는데 채점할때 1,2번이 안돼서 시간을 많이 잡아먹었다..

알파벳 순으로 했을때 안되는게 있을 수 있다 - 그 경우는 다른 방식을 찾아야한다

 

무튼 count가  tickets.length일때만 저장을 해야한다.

그래서 str에 계속 붙이다가 count가 size일때 리스트에 넣어주었고

리스트는 알파벳순으로 정렬해서

가장 첫번째 요소를 출력하도록 하였다.

중간에 잘못 갔을때는 visit이랑 str(route)를 이전으로 되돌려 주어야한다.

아마 1번인지 2번인지 테케가 안되는 이유는 밑에 예시 때문일 것이다.

ex) ["ICN", AAA], [AAA,CCC], [AAA,DDD], [DDD,AAA] 

여기서 aaa ccc를 먼저가게 되면 답이 안나오기 때문에 다시 탐색을 해야한다.

 

이부분을 떠올리는게 가장 어려웠다..

처음에는 스택으로도 해보고 다해봤는데 안돼서 결국은 다른 블로그를 참고해서 문자열로 붙이기로 했다

다른 방법은 생각이 나지 않는다..

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    int[] visited;
    String str = "";
    ArrayList<String> list = new ArrayList<String>();
    public void dfs(String current,int count,String[][] tickets ){
        str+= current+",";
        if(count == tickets.length){
           list.add(str);
            return ;
        }

        for(int i=0;i<tickets.length;i++){
            if(visited[i]!=1&&tickets[i][0].equals(current)){
                visited[i]=1; 
                dfs(tickets[i][1],count+1,tickets);
                visited[i]=0;
                str = str.substring(0,str.length()-4);        
            }
        }
    }
    public String[] solution(String[][] tickets) {
        
        int size=tickets.length;
        visited=new int[size];
        
        for(int i=0;i<size;i++){
            if(tickets[i][0].equals("ICN")){
                visited[i]=1;
                str="ICN,";
                dfs(tickets[i][1],1,tickets);
                visited[i]=0;
            }
        }
        Collections.sort(list);
		String[] answer = list.get(0).split(",");
        return answer;
    }
}