[프로그래머스] 여행경로 Java 풀이 및 해설

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

프로그래머스

 

풀이 방법

• DFS를 사용한다.
• dfs(남은 티켓, 현재 공항, 현재까지의 누적 경로, 정답 후보(미정렬상태), 티켓 사용 여부, 티켓)
• 모든 티켓을 사용했다면 정답 후보에 넣는다.
• 티켓 반복문을 돌며 현재 공항과 티켓에 명시된 출발지가 동일하다면 depth + 1을 한다.
• 단, 미사용 티켓이여야한다.

모든 티켓을 사용했을때 정답 후보에 경로를 ","를 구분자로 넣는다.

DFS 탐색을 종료하고 오름차순으로 정렬하고 "," 구분자가 있으므로 첫번째 스트링을 split(",")로 분리한것이 답이다.

 

전체 코드

import java.util.*;
class Solution {
    
    public String[] solution(String[][] tickets) {
        String[] answer;
        
        List<String> pathList = new ArrayList<>();
        boolean[] visit = new boolean[tickets.length];
        dfs(tickets.length, "ICN", "ICN", pathList, visit, tickets);
        
        pathList.sort((o1, o2) -> {
            return o1.compareTo(o2);
        });
        
        answer = pathList.get(0).split(",");
    
        return answer;
    }
    
    void dfs(int leaveTicket, String cur, String path, List<String>pathList, boolean[] visit, String[][] tickets) {
        if(leaveTicket == 0) {
            pathList.add(path);
            return;
        }
        
        for(int i=0; i<tickets.length; i++) {
            String ticketStart = tickets[i][0]; // 티켓의 출발지
            String ticketGoal = tickets[i][1]; // 티켓의 목적지
            
            if(ticketStart.equals(cur) && visit[i] == false) {
                visit[i] = true;
                dfs(leaveTicket-1, ticketGoal, path+","+ticketGoal, pathList, visit, tickets);
                visit[i] = false;
            }
        }
    }
}