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

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

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

 

문제 요약

출발지와 도착지로 이루어진 티켓의 배열이 주어진다. "ICN"부터 시작해서 티켓을 모두 소모하여 경로 배열을 반환해야 한다. 티켓을 모두 소모할 수 있는 방법이 2개 이상이라면 사전 순으로 가장 앞선 방법을 선택하면 된다.

 

문제 풀이

 이 문제 또한 DFS를 사용해서 풀었다. 문제 난이도는 크게 어려울 게 없었고, 사전순으로 빠른 경로를 찾기 위해 정렬해 주는 부분만 생각해주면 되는 문제이다. 

 

 우선 티켓의 사용 여부를 저장할 boolean 배열 used와 경로를 담을 문자열 배열 answer 배열을 선언했다. 그리고 티켓을 모두 사용한 경우를 사전순으로 찾기 위해서 티켓 배열을 도착지 사전순으로 정렬하였다. DFS 함수에서는 종료조건으로 경로배열의 마지막 요소가 채워져있다면 return 하도록 하였고, 티켓을 사용하지 않았으면서 현재 위치와 출발지 위치가 동일한 티켓을 찾아서 탐색했다.

 

나의 코드

import java.util.*;

class 여행경로 {
    boolean[] used; //  표를 사용했는지 저장하는 boolean 배열
    String[] answer; // 경로 문자열 배열

    public String[] solution(String[][] tickets) {
        used = new boolean[tickets.length];
        answer = new String[tickets.length + 1];

        // 티켓 배열을 도착지 사전순으로 정렬하고 dfs 실행
        Arrays.sort(tickets, Comparator.comparing(t -> t[1]));
        dfs(0, "ICN", tickets);

        return answer;
    }

    /* dfs 경로 찾기 함수 */
    public void dfs(int depth, String now, String[][] tickets) {
        // 경로를 모두 채웠을 때 종료
        if (answer[tickets.length] != null)
            return;

        answer[depth] = now;

        for (int i = 0; i < tickets.length; ++i) {
            if (!used[i] && tickets[i][0].equals(now)) {
                used[i] = true;
                dfs(depth + 1, tickets[i][1], tickets);
                used[i] = false;
            }
        }
    }
}