프로그래머스 여행경로 자바 풀이

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

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

여행경로 문제에 대해서 DFS로 풀어보자.

모든 경로를 사용해야 하므로 tickets.length와 현재 뎁스 카운트가 같아지면 재귀를 탈출하게 짰다.

처음엔 간선이 주어졌다 생각하고 공항들을 숫자로 바꿔 해야 하나 했지만 복잡해 풀이를 찾아보니 간단하게 문자열로 나열, 덧붙이는 방법이 있었다. 이를 나중에 공백으로 쪼개어 배열에 넣어주어 리턴하면 된다.

 

솔직히 조금 어려웠다! 그렇지만 지금 수준에서 어렵지 않은 문제는 없는 것 같다..

 

프로그래머스에 옮겨 넣을 때 import 해주는 것을 잊지 말자.

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

public class TravelRoute {

    ArrayList<String> routes = new ArrayList<>();
    boolean[] visit;

    public String[] solution(String[][] tickets) {

        visit = new boolean[tickets.length];

        DFS(tickets, "ICN", "ICN", 0);

        Collections.sort(routes);

        String[] answer = routes.get(0).split(" ");

        return answer;
    }

    public void DFS(String[][] tickets, String start, String route, int cnt) {
        if(cnt == tickets.length) {
            routes.add(route);
            return;
        }

        for(int i = 0; i < tickets.length; i ++) {
            if(!visit[i] && tickets[i][0].equals(start)) {
                visit[i] = true;
                DFS(tickets, tickets[i][1], route + " " + tickets[i][1], cnt + 1);
                visit[i] = false;
            }
        }
    }
}