Programmers - 여행경로 with JAVA

 

 

프로그래머스 문제 중 '여행경로' 문제에 대해서 블로그를 작성해보려고 한다.

 

우선, 입력은 다음과 같이 티켓이 주어진다.

[[ICN, JFK] , [HND, IAD], [JFK, HND]]

 

조건은 다음과 같다.

1. 출발지는 ICN이다.

2. 모든 티켓을 사용한다.

3. 경로가 여러개라면 알파벳 순으로 정렬해서 첫번째 티켓을 출력한다.

나머지는 길이나 부가적인 조건이다.

 

출력은 다음과 같다.

[ICN, JFK, HND, IAD] 와 같이 경로를 출력한다.

 

 

구현

1. 출발지는 ICN이다

-> for문을 돌며 티켓의 시작이 ICN이면 DFS를 돌린다.

2. 모든 티켓을 사용한다.

-> DFS를 돌며 티켓의 길이가 다 찼을때, 반환시킨다.

3. 알파벳 정렬

-> 티켓이 여러개일 경우

-> String으로 나열 후, 값에 대한 인덱스를 해시로 저장

-> String을 나열된 값 정렬

-> 정렬된 첫번째 값의 해당하는 인덱스의 해당하는 값 출력

 

 

코드

import java.util.*;
class Solution {
    private static List<List<String>> check = new ArrayList<>();
    public List<String> solution(String[][] tickets) {
        Boolean[] visited = new Boolean[tickets.length];
        Arrays.fill(visited, false);
        for(int i=0; i<tickets.length; i++){
            if(tickets[i][0].equals("ICN")){
                visited[i] = true;
                List<String> now = new ArrayList<>();
                now.add(tickets[i][0]);
                now.add(tickets[i][1]);
                dfs(tickets, now, visited, tickets[i][1], 2);
                visited[i] = false;
            }   
        }
        if(check.size() == 1){
            return check.get(0);
        }
        HashMap<String, Integer> hash = new HashMap<>();
        List<String> sorted_value = new ArrayList<>();
        for(int j=0; j<check.size(); j++){
            String value = "";
            for(int i=0; i<check.get(j).size(); i++){
                value += check.get(j).get(i);
            }
            hash.put(value, j);
            sorted_value.add(value);
        }
        Collections.sort(sorted_value);
        return check.get(hash.get(sorted_value.get(0)));
    }
    public void dfs(
        String[][] tickets, List<String> now,
        Boolean[] visited, String next, int index){
        int count = 0;
        for(Boolean v : visited){
            if(!v){
                break;
            }
            count += 1;
        }
        if(now.size() == tickets.length + 1 
           & count == tickets.length & now.get(0).equals("ICN")){
            check.add(new ArrayList<>(now));
            return;
        }
        
        for(int i=0; i<tickets.length; i++){
            if(visited[i] == true){
                continue;
            }
            if(tickets[i][0].equals(next)){
                visited[i] = true;
                now.add(tickets[i][1]);
                bfs(tickets, now, visited, tickets[i][1], index+1);
                now.remove(index);
                visited[i] = false;
            }            
        }
    }
}