[알고리즘] 프로그래머스 - 여행경로(dfs/bfs)

1. 문제

2. 문제풀이

처음에 풀때 인접행렬을 이용해서 인접행렬의 방문한 곳은 다시 방문하지 않는 형태로 풀었었다. 하지만 항공사를 여러번 방문 할 수 있기 때문에 인접행렬이아닌, 항공권을 사용했는지를 체크하는 형태로 바꾸었다. 주어진 조건중에 알파벳 순서가 앞서는 경로를 return 하라는 조건을 각 배열을 정렬해야하나 했다가 String으로 방문 가능한 경로를 ','로 이어주고 그 Stirng들을 저장한 list를 정렬하는 방식으로 수정하였다.

 

1. 출발 항공사가 "ICN"일 경우 그 항공권을 사용했다고 표시해주고 dfs알고리즘을 호출한다.

2. route에 현재 경로를 더해주고, 현재 사용하지 않은 티켓중에 이전 도착지와 현재 티켓의 출발지가 같다면 티켓을 사용했다고 표시하고 dfs 알고리즘을 다시 호출 한다.

3. 호출 회수와 티켓의 개수가 같다면 list에 현재까지의 route경로를 저장한다.

4. 경로를 저장한 list를 오름차순으로 정렬하면 알파벳 순서가 앞서는 경로가 리스트이 0번째 인덱스에 저장된다.

5. ","단위로 문자열을 쪼개 answer 배열에 담아서 return 한다.

import java.util.*;

class Solution {
    
    boolean[] visit;
    List<String> list = new ArrayList<>();
    
    public void dfs(String[][] tickets, String preDesti, String route, int depth) {
        
        route += preDesti + ",";
        
        if(depth == tickets.length){
            list.add(route);
            return;
        }
        
        for(int i = 0 ; i < tickets.length ; i++) {
            String depart = tickets[i][0];
            String desti = tickets[i][1];
			
            if(preDesti.equals(depart) && !visit[i]) {
                visit[i] = true;
                dfs(tickets, desti, route, depth+1);
                visit[i] = false;
            }
        }        
        
    }

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        int len = tickets.length;
        visit = new boolean[len];
        String route = "";
        
        for(int i = 0 ; i < len; i++) {
            String depart = tickets[i][0];
            String desti  = tickets[i][1];
			
            if(depart.equals("ICN")) {
                visit[i] = true;
                route = depart + ",";
                dfs(tickets, desti, route, 1);
                visit[i] = false;
            }
        }        
        
        Collections.sort(list);
        answer = list.get(0).split(",");
        
        for(int i=0;i<answer.length;i++){
            System.out.println(answer[i]);
        }
        
        return answer;
    }
}