[Lv.3] 여행경로 : Java

프로그래머스

 

 

 

 

이해하기

[DFS] 프로그래머스 여행경로 "JAVA"

참고한 블로그 링크...

dfs를 사용하되 파라미터로 start(출발지), route(지금까지의 경로), tickets, count(사용한 티켓 수)를 넘겨준다.

 

 

 

문제풀이

import java.util.*;

class Solution {
    ArrayList<String> list;
    boolean[] visited;

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        int count = 0;
        visited = new boolean[tickets.length];
        list = new ArrayList<>();

        dfs("ICN", "ICN", tickets, count);

        Collections.sort(list);
        answer = list.get(0).split(" ");

        return answer;
    }

    public void dfs(String start, String route, String[][] tickets, int count) {
        if (count == tickets.length) {
            list.add(route);
            return;
        }

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

 

    ArrayList<String> list;
    boolean[] visited;

 

경로를 저장할 list와 방문처리를 위한 visited

 

        String[] answer = {};
        int count = 0;
        visited = new boolean[tickets.length];
        list = new ArrayList<>();

 

사용한 티켓 수를 셀 count 변수를 만들어준다.

 

        dfs("ICN", "ICN", tickets, count);

 

출발지는 ICN이고, 이미 ICN을 방문하였으므로 route에 ICN을 미리 담아준다.

 

        if (count == tickets.length) {
            list.add(route);
            return;
        }

 

dfs 함수를 돌다가 만약 티켓을 전부 사용했다면 list에 route를 저장해주고 return해준다.

 

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

 

티켓을 전부 돌면서, 출발지로부터 출발하고, 아직 사용하지 않은 티켓이라면 if문 내부를 실행한다.

방문 처리해주고, dfs에 사용한 티켓의 도착지를 넣어주고, route에 다음 경로를 더해준다.

예를 들어 "ICN", "JFK"라는 티켓을 사용한다면 route = "ICN JFK"가 된다.

 

이 부분이 신기한 풀이방법이라고 생각했다.

 

        Collections.sort(list);
        answer = list.get(0).split(" ");

 

다시 solution 함수로 돌아와서 list를 정렬해준다. (알파벳 순서가 빠른 경로를 반환할 것이기 때문)

list의 0번째 값을 가져오되, String 배열을 return해야하므로 split(" ")을 사용하여 배열화해준다.