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

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

 

 

언제인지 모를, 기존에 짜둔 코드. -> 테케 1번 통과 못함. 

import java.util.*;

class Solution {
    
    public static boolean visit[];
    public static ArrayList <String> list; 
    public static ArrayList <String> result;
    
    public String[] solution(String[][] tickets) {
        // 일단 ICN부터 시작하기 -> ICN 2개 이상이면 각자 탐색 ㄱㄱ
        // 더 이상 방문할 수 있는 도시가 없다면 끝
        // ticket의 개수만큼 모두 돌았다면 = 모두 visit 했다면 -> return에 담기
        // 가능한 경로가 2개 이상이면 알파벳 순으로 비교해서 return에 담기. 
        
        visit = new boolean[tickets.length];
        list = new ArrayList<>(); // dfs에 경로 탐색하며 문자열 담을 때 사용. 
        result = new ArrayList<>(); // 경로 끝까지 탐색했을 때 모든 경로 담기 위해 사용
        ArrayList <String> finale = new ArrayList<>(); // 최종 리턴할 리스트
        
        // ICN이 있는 모든 배열을 찾아서 DFS 시작점으로 돌리기 
        for (int i =0; i<tickets.length; i++){
            if(tickets[i][0].equals("ICN")){
                dfs(tickets, i, visit, list, result); // 값 비교 해서 알파벳 비교해서 담기
                if (finale.isEmpty()){
                    finale.addAll(result); 
                }
                else{
                    for (int k =0; k< result.size(); k++){
                        int compare = result.get(k).compareTo(finale.get(k));
                        if (compare == 0) continue;
                        else if (compare > 0) break; // finale가 사전순으로 앞섬 
                        else { 
                            finale.clear();
                            finale.addAll(result);
                        }
                    }
                }
                list.clear();
                result.clear();
                visit = new boolean[tickets.length]; //다시 초기화
            }
        }
        
        String[] answer = new String[finale.size()];
        finale.toArray(answer);        
        
        return answer;
    }
    
    // class 밑단에서 바로 선언된 변수들은 dfs 파라미터에 담을 필요가 있나? 
    
    public void dfs(String[][] tickets, int cur, boolean[] visit, ArrayList<String> list, ArrayList<String> result){
        list.add(tickets[cur][0]); //list add
        visit[cur] = true; // 방문 표시
        
        int count = 0;
        for (int j = 0; j<tickets.length; j++){
            if (visit[j]==true) count++; //방문한 곳 count
        }
        if (count == tickets.length) {
            // 끝까지 경로를 탐색했다면, 탐색한 경로끼리 비교하여서 알파벳 앞서는 경로를 담아야함.
            // 일단 첫번째로 탐색된 경로를 담을 변수 필요. 
            list.add(tickets[cur][1]);// 마지막 경로도 담아주기. 
            if (result.isEmpty()){ // 첫번째로 끝까지 탐색된 경로라면
                result.addAll(list);
            }
            else { // 알파벳 비교하기
                for (int i =0; i< result.size();i++){
                    int compare = result.get(i).compareTo(list.get(i));
                    if (compare == 0) continue;
                    else if (compare > 0){ // list가 사전순으로 앞섬 
                        result.clear();
                        result.addAll(list);
                    } 
                    else break;
                }
            }
        }
        
        for(int j =0; j<tickets.length; j++){
            if (tickets[cur][1].equals(tickets[j][0]) && !visit[j]){
                dfs(tickets, j, visit, list, result); // 값 비교 해서 알파벳 비교해서 담기
                visit[j] = false;
            }
        }
    }
}

 

 

 

여튼, 위에 코드 써둔거 안읽고, 다시 풀어봤는데 이번엔 맞음. 위에선 멀 간과했을까.. 

풀이 방식은

1. tickets 배열을 탐색하면서. 티켓이 "ICN"으로 출발하는 티켓이면 DFS 탐색을 한다. 

2. 탐색하면서 찾은 경로는 다 ArrayList 배열에 add 한다.

3. 탐색 끝났을 때, 찾은 경로가 2개 이상이면 알파벳 비교해서 앞선 알파벳 배열로 return 한다. 

 

import java.util.*;

class Solution {
    
    static ArrayList<String[]> road = new ArrayList<>();
    
    public String[] solution(String[][] tickets) {
        
        // 만약 티켓이 "ICN"에서 출발하는 티켓이면, DFS 탐색하기
        for (int i = 0; i < tickets.length; i++){
            if (tickets[i][0].equals("ICN")){
                
                // 경로배열의 크기 = ticket크기 - 1
                String[] arr = new String[tickets.length+1];
                arr[0] = tickets[i][0];
                arr[1] = tickets[i][1];
                
                // 방문 체크하기
                boolean visited[] = new boolean[tickets.length];
                visited[i] = true;
                
                    
                // 0,1 인덱스는 이미 담겼으니까 2부터 시작하기. 
                dfs(2, arr, tickets, visited);
            }
        }
        
        
        String[] return_road = road.get(0);
        
        // list 돌아가면서 알파벳 순서 비교하기
        if (road.size() >= 2){
            
            for (int i = 1; i < road.size(); i++){
                String[] compare = road.get(i);
                for (int j = 0; j < return_road.length; j++){
                    // 만약 compare[j]가 return_road[j]보다 앞선다면 업데이트 하기.
                    if (compare[j].compareTo(return_road[j]) < 0){
                        return_road = compare;
                        break;
                    }
                    else if(compare[j].compareTo(return_road[j]) > 0){
                        break;
                    }
                }
            }
        }
        // for (String str : return_road){
        //     System.out.print(str+" ");
        // }
        
        return return_road;
    }
    
    static public void dfs(int depth, String[] arr, String[][] tickets, boolean visited[]){
        
        // 만약 arr에 모든 배열 담겼으면 list에 add
        if (depth == arr.length){
            String[] copy = Arrays.copyOf(arr, arr.length);
            road.add(copy);
            return;
        }
        
        for (int i = 0; i < tickets.length; i++){
            // 아직 방문하지 않았고, 현재 티켓 도착지 = 다음 티켓 출발지 이면 arr에 담고 dfs 탐색
            if (visited[i]) continue;
            
            // 왜 마지막 원소가 안 담길까 .. 
            if (tickets[i][0].equals(arr[depth-1])){
                
                arr[depth] = tickets[i][1];
                visited[i] = true;
                dfs(depth+1, arr, tickets, visited);
                visited[i] = false;
                
            }  
        }
        
        
    }
}