[JAVA] DFS/BFS "여행경로"

 

ArrayList에 하나씩 값을 넣어야한다는 편견을 깨주었다.

한가지의 순서를 각각의 list[i]에 value + " " + value2 를 하여 일련의 String을 이어붙이고

 

이를 sort하여 가장 낮은차순의 배열을 추출할때 사용한다.

 

import java.util.ArrayList;
import java.util.Collections;
 
public class TravelRoute {
    boolean[] visited;                    //방문한지 안한지를 체크하는 visited배열
    ArrayList<String> answers;
 
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];    
        answers = new ArrayList<String>();
        int count = 0;                                    //몇개의 공항을 들렸는지 알려주는 카운트
        dfs(count, "ICN", "ICN",tickets);                
        Collections.sort(answers);                        //답들 중 가장 알파벳순이 빠른 배열들로 정렬
        String[] answer = answers.get(0).split(" ");    //가장 빠른 배열을 뽑아서 String형 배열로 만듬
        return answer;
    }
    public void dfs(int count, String present, String answer, String[][]ticktes) {
        if(count == ticktes.length) {            //모든 공항을 들렸다면
            answers.add(answer);                //answers에 추가
            return;
        }
        for(int i = 0; i < ticktes.length; i++) {
            if(!visited[i] && ticktes[i][0].equals(present)) {//present와 같고 들리지 않은 공항을 찾고
                visited[i] = true; //해당 공항을 들린걸로 만듬.
                
                //카운트 +1 도착 공항을 present로 넣어주고 answer에 도착공항을 추가해준다.
                dfs(count+1, ticktes[i][1],answer+" "+ticktes[i][1] , ticktes);    
                visited[i] = false;
            }
        }
        return;
    }

 

visited를 잘 활용해야한다. 위에서 설명한 방식대로 재귀를 이용하면 답을 구할수 있다.

tosuccess.tistory.com/36

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