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

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

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

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

풀이

백트랙킹 + 순열을 사용해서 풀었다. 뽑는 순서에 따라 결과가 달라지기 때문이다. 또한 백트랙킹으로 조건에 맞는 모든 경우를 탐색하도록 하였다.

 

이때 중요한 점은 뽑을 수 있는 순서가 여러개가 될 수 있으며, 이 중에서 알파벳 순서가 앞서는 경로만을 return해야 한다. 아래 예제 2를 읽어보면 이해가 될 것이다.

 

그러므로 이를 처리하기 위해 모든 경로에 대한 값을 arraylist에 담고, 백트랙킹이 끝난 후 list를 sorting해준다.

그런 다음 제일 첫 인덱스의 값을 배열로 만들어서 return해주면 된다.

 

 

코드

import java.util.*;
 
class Solution {
    
    ArrayList<String> list;
    boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        list = new ArrayList<>();
        visited = new boolean[tickets.length];
        
        backtracking("ICN", 0, "ICN",tickets);
        Collections.sort(list);
        String[] result = list.get(0).split(" ");
        return result;
    }
    
    public void backtracking(String s, int idx, String result, String[][] tickets) {
        if(idx == tickets.length) {
            list.add(result);
            return;
        }
        
        for(int i = 0; i < tickets.length; i++) {
            if(visited[i] == false && tickets[i][0].equals(s)) {
                visited[i] = true;
                backtracking(tickets[i][1], idx + 1, result + " " + tickets[i][1], tickets);
                visited[i] = false;
            }
        }
    }
}