LV3 - 여행경로 (Java)

 

---

 

문제

 

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

프로그래머스

 

 

풀이

 

단순 dfs로 풀이했다.

 

우선 들어오는 값을 Map 형태로 저장했다.

key에는 시작점을 넣었고, value 에는 List 형태로 도착점을 저장했다. 이 때 Node 라는 클래스를 이용해서 visit 필드로 해당 티켓을 사용했는지 판단했다.

 

그리고 사전순으로 방문해야하기에 도착점을 기준으로 정렬했다.

 

이후에는 ICN을 시작으로 dfs 를 수행했다.  정렬을 했기에 사전순으로 앞선 값들을 먼저 방문한다. 계속 방문하다가 모든 티켓을 사용하였다면 그게 답이 될것이고, 아니라면 되돌아가서 다른 경로를 찾게 된다.

 

코드

import java.util.*;

class Solution {

    static class Node {
        public String val;
        public boolean visit;
        
        public Node(String val, boolean visit){
            this.val = val;
            this.visit = visit;
        }
    }
    
    static List<String> answer = new ArrayList<>();
    
    public void dfs(Map<String, List<Node>> map, String key, int now, int limit, List<String> ans){

        if(now >= limit){
            if(answer.size() == 0){
                for(String str : ans) answer.add(str);
            }
            return;
        }
        
        if(!map.containsKey(key)) return;
        
        for(Node node : map.get(key)){
            if(!node.visit){
                node.visit = true; // 티켓 사용 처리
                List<String> temp = new ArrayList<>(ans);
                temp.add(node.val); // 정답에 추가
                dfs(map, node.val, now+1, limit, temp);
                node.visit = false;
            }
        }
    }
    
    
    public List<String> solution(String[][] tickets) {
        
        // Initialize
        Map<String, List<Node>> map = new HashMap<>();
        
        for(int i=0; i<tickets.length; i++){
            String from = tickets[i][0];
            String to = tickets[i][1];
            
            if(!map.containsKey(from)){
                List<Node> list = new ArrayList<>();
                list.add(new Node(to, false));
                map.put(from, list);
            } else{
                map.get(from).add(new Node(to, false));
            }
        }
        
        // list 값들을 알파벳 오름차순으로 정렬
        for(String key : map.keySet()){
            map.get(key).sort((o1, o2) -> o1.val.compareTo(o2.val));
        }
        
        List<String> ans = new ArrayList<>();
        ans.add("ICN");
        
        // map, 시작점, 티켓 사용량, 티켓 최대, 정답 리스트
        dfs(map, "ICN", 0, tickets.length, ans);
        
        return answer;
    }
}

 

후기