[Java/프로그래머스/DFS] 여행경로

문제

programmers.co.kr/learn/courses/30/lessons/43164

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

 

코드

처음엔 인접하는 공항들을 전부 adjacent에 넣어야 하는데 어떻게 해야할까 끙끙댔다. 다행히 tickets는 양방향이 아닌 순서가 있는 것이라, dfs함수의 if문에서 조건을 걸러낼 수 있었다.

import java.util.ArrayList;
import java.util.Collections;
 
public class Solution {
    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형 배열로 만듬
        
        for(String s : answers){
            System.out.println(s);
        }
        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;                                    //해당 공항을 들린걸로 만듬.
                dfs(count+1, ticktes[i][1],answer+" "+ticktes[i][1] , ticktes);    //카운트 +1 도착 공항을 present로 넣어주고 answer에 도착공항을 추가해준다.
                visited[i] = false;
            }
        }
        return;
    }
}

 

위 코드를 돌려보면 ArrayList<String> answers에 가능한 경로가 전부 들어온다.

answers를 출력해보면,

이렇게 나온다. 가능한 경로가 2개 이상인 경우를 대비해서 알파벳 순서가 앞서는 경로를 return하도록 했다.

(경로에 해당하는 공항이름을 전부 String에 담은 이유 → Collectons.sort(answers));