[240411] 알고리즘 리부트 48일차 - 프로그래머스 여행경로 자바

 

[정답코드]

인접리스트에 매몰되었음... 해시 맵을 우선순위 큐와 조합해서 유사하게 구현 가능하며 정렬까지도 한 번에 해결해 줌. 재귀가 끝나는 순서대로 답에 담기기 때문에 역순처리 해주기

import java.util.*;

class Solution {
    
    public static ArrayList<String> answer;
    public static HashMap<String, PriorityQueue<String>> tks;


    public String[] solution(String[][] tickets) {
                
        answer = new ArrayList<>();
        tks = new HashMap<>();
        
        for(String[] ticket : tickets){
            tks.putIfAbsent(ticket[0], new PriorityQueue<>());
            tks.get(ticket[0]).add(ticket[1]);
        }
        
        tour("ICN");
        
        Collections.reverse(answer);      
        
        return answer.toArray(new String[0]);
    }
    
    public static void tour(String depart){
        
        while(tks.containsKey(depart) && !tks.get(depart).isEmpty()){
            
            String arrival = tks.get(depart).poll();            
            tour(arrival);
               
        }
                
        answer.add(depart);
        
    }
}

 

[실패 코드]

끝까지 이어질 수 없는 경우를 고려하지 못한 경우

import java.util.*;

class Solution {
    public static HashMap<String[], Boolean> used;
    public static HashMap<String, Integer> airport;
    public static ArrayList<String>[] tks;
    public static ArrayList<String> answer;
    
    public String[] solution(String[][] tickets) {
        
        used = new HashMap<>();        
        airport = new HashMap<>();
        answer = new ArrayList<>();
        
        int idx = 0;
        
        // 각 공항을 인덱스 하기 위한 처리 + 티켓 사용 처리
        for(String[] ticket : tickets) {
            if(!airport.containsKey(ticket[0])) {
                airport.put(ticket[0], idx++);
            }
            used.put(ticket, false);
        }       
        
        tks = new ArrayList[airport.size()];
        
        // 리스트로 초기화
        for(int i = 0; i < airport.size(); i++) {
            tks[i] = new ArrayList<String>();
        }
        
        // 인접리스트에 넣기
        for(String[] ticket : tickets) {
            tks[airport.get(ticket[0])].add(ticket[1]);
        }
        
        // 알파벳 순으로 정렬
        for(int i = 0; i < airport.size(); i++) {
            Collections.sort(tks[i]);
        }        
        
        answer.add("ICN");
        tour("ICN"); 
        
        return answer.stream().toArray(String[]:: new);
    }
    
    public static void tour(String depart){
        
        if(noMoreTicket()) return;
        
        int idx = airport.get(depart);
        
        for(int i = 0; i < tks[idx].size(); i++){
            String next = tks[idx].get(i);
            
            // 아직 사용하지 않았다면            
            if(!usedOrNot(depart, next)){ 
                answer.add(next); // 정답 리스트에 더하고
                makeUsed(depart, next); // 사용한 티켓 처리
                tour(next);
            }
        }
    }
        
    public static boolean usedOrNot(String depart, String arrival){
        for(String[] key : used.keySet()){
            if(depart.equals(key[0]) && arrival.equals(key[1]) && used.get(key)) return true;
        }
        return false;
    }
    
    public static void makeUsed(String depart, String arrival){
        for(String[] key : used.keySet()){
            if(depart.equals(key[0]) && arrival.equals(key[1])){
                used.put(key, true);
            } 
        }
    }
    public static boolean noMoreTicket(){
        for(String[] key : used.keySet()){
            if(!used.get(key)) return false;
        }
        
        return true;
    }
}

직후에 이어지는 공항에서 출발하는 티켓이 없는 경우를 예외처리

import java.util.*;

class Solution {
    public static HashMap<String[], Boolean> used;
    public static HashMap<String, Integer> airport;
    public static ArrayList<String>[] tks;
    public static ArrayList<String> answer;
    public static String before;
    
    public String[] solution(String[][] tickets) {
        
        used = new HashMap<>();        
        airport = new HashMap<>();
        answer = new ArrayList<>();
        
        int idx = 0;
        
        // 각 공항을 인덱싱하기 위한 처리 + 티켓 사용 처리
        for(String[] ticket : tickets) {
            if(!airport.containsKey(ticket[0])) {
                airport.put(ticket[0], idx++);
            }
            used.put(ticket, false);
        }       
        
        tks = new ArrayList[airport.size()];
        
        // 리스트로 초기화
        for(int i = 0; i < airport.size(); i++) {
            tks[i] = new ArrayList<String>();
        }
        
        // 인접리스트에 넣기
        for(String[] ticket : tickets) {
            tks[airport.get(ticket[0])].add(ticket[1]);
        }
        
        // 알파벳 순으로 정렬
        for(int i = 0; i < airport.size(); i++) {
            Collections.sort(tks[i]);
        }        
        
        answer.add("ICN");
        tour("ICN"); 
        
        return answer.stream().toArray(String[]:: new);
    }
    
    public static void tour(String depart){
        
        if(noMoreTicket()) return;
        
        if(!airport.containsKey(depart)){ // 이어질 수 없으면 원복처리
            answer.remove(depart);
            makeUnused(before, depart);
            return;
        }
        
        int idx = airport.get(depart);
        
        for(int i = 0; i < tks[idx].size(); i++){
            String next = tks[idx].get(i);
            
            // 아직 사용하지 않았다면            
            if(!usedOrNot(depart, next)){ 
                answer.add(next); // 정답 리스트에 더하고
                makeUsed(depart, next); // 사용한 티켓 처리
                before = depart;
                tour(next);
            }
        }
        
    }
        
    public static boolean usedOrNot(String depart, String arrival){
        for(String[] key : used.keySet()){
            if(depart.equals(key[0]) && arrival.equals(key[1]) && used.get(key)) return true;
        }
        return false;
    }
    
    public static void makeUsed(String depart, String arrival){
        for(String[] key : used.keySet()){
            if(depart.equals(key[0]) && arrival.equals(key[1])){
                used.put(key, true);
            } 
        }
    }
    
    public static void makeUnused(String depart, String arrival){
        for(String[] key : used.keySet()){
            if(depart.equals(key[0]) && arrival.equals(key[1])){
                used.put(key, false);
            } 
        }
    }
    public static boolean noMoreTicket(){
        for(String[] key : used.keySet()){
            if(!used.get(key)) return false;
        }
        
        return true;
    }
}

동일한 경로를 가진 티켓을 고려해서 boolean 대신 Integer로 처리했으나 직후 경로는 존재하나 끝까지 이어지지 못하는 경로를 선택하는 경우를 배제하지 못함 

import java.util.*;

class Solution {
    public static HashMap<String[], Integer> used;
    public static HashMap<String, Integer> airport;
    public static ArrayList<String>[] tks;
    public static ArrayList<String> answer;
    public static String before;
    
    public String[] solution(String[][] tickets) {
        
        used = new HashMap<>();        
        airport = new HashMap<>();
        answer = new ArrayList<>();
        
        int idx = 0;
        
        // 각 공항을 인덱싱하기 위한 처리 + 티켓 사용 처리
        for(String[] ticket : tickets) {
            if(!airport.containsKey(ticket[0])) {
                airport.put(ticket[0], idx++);
            }
            used.put(ticket, used.getOrDefault(ticket, 0)+1);
        }
        
        tks = new ArrayList[airport.size()];
        
        // 리스트로 초기화
        for(int i = 0; i < airport.size(); i++) {
            tks[i] = new ArrayList<String>();
        }
        
        // 인접리스트에 넣기
        for(String[] ticket : tickets) {
            tks[airport.get(ticket[0])].add(ticket[1]);
        }
        
        // 알파벳 순으로 정렬
        for(int i = 0; i < airport.size(); i++) {
            Collections.sort(tks[i]);
        }        
        
        answer.add("ICN");
        tour("ICN"); 
        
        return answer.stream().toArray(String[]:: new);
    }
    
    public static void tour(String depart){
        
        if(noMoreTicket()) return;
        
        if(!airport.containsKey(depart)){ // 이어질 수 없으면 원복처리
            answer.remove(depart);
            makeUnused(before, depart);
            return;
        }
        
        int idx = airport.get(depart);
        
        for(int i = 0; i < tks[idx].size(); i++){
            String next = tks[idx].get(i);
            
            // 아직 사용하지 않았다면            
            if(usedOrNot(depart, next)){ 
                answer.add(next); // 정답 리스트에 더하고
                makeUsed(depart, next); // 사용한 티켓 처리
                before = depart;
                tour(next);
            }
        }
        
    }
        
    public static boolean usedOrNot(String depart, String arrival){
        for(String[] key : used.keySet()){
            if(depart.equals(key[0]) && arrival.equals(key[1]) && used.get(key) > 0) return true;
        }
        return false;
    }
    
    public static void makeUsed(String depart, String arrival){
        for(String[] key : used.keySet()){
            if(depart.equals(key[0]) && arrival.equals(key[1])){
                used.put(key, used.getOrDefault(key, 0)-1);
            } 
        }
    }
    
    public static void makeUnused(String depart, String arrival){
        for(String[] key : used.keySet()){
            if(depart.equals(key[0]) && arrival.equals(key[1])){
                used.put(key, used.getOrDefault(key, 0)+1);
            } 
        }
    }
    public static boolean noMoreTicket(){
        for(String[] key : used.keySet()){
            if(used.get(key)>0) return false;
        }
        
        return true;
    }
}