[프로그래머스] 여행경로 (Java)

문제

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

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

풀이

처음에 방문 체크를 HashSet을 이용했었고 예제가 맞아서 제출을 했지만 

1번, 2번 테스트 케이스에서 런타임에러가 발생하였다. 

원인은.... 바로 중복 티켓이 허용된다는 것이다. 

다음과 같이 from-to가 동일한 티켓이 포함될 수있다.

Tickets: [["ICN", "SFO"], ["SFO", "ICN"], ["ICN", "SFO"], ["SFO", "QRE"]]

 

따라서 HashSet을 중복체크로 사용하면 안된다. 

나의 경우는 방문체크할 자료형을 HashMap으로 사용하였다.

Key를 from,to 문자열 / Value는 해당 경로의 티켓 개수로 지정하여 

방문, 방문취소 처리할 때마다 해당 Count를 변경해주었다.

 

소스코드

import java.util.*;
class Solution {
    HashMap<String, ArrayList<String>> map;
    HashMap<String, Integer> remainedTickets;
    ArrayList<String> result;
    int pathCnt; 
    public String[] solution(String[][] tickets) {
        String[] answer = {};

        this.pathCnt = tickets.length;
        this.result = new ArrayList<String>();
        this.remainedTickets = new HashMap<String, Integer>();
        this.map = new HashMap<String, ArrayList<String>>();
        for(int i = 0; i < tickets.length; i++){
            String key = tickets[i][0];
            String val = tickets[i][1];
            if(!map.containsKey(key)){
                map.put(key, new ArrayList<String>(){{add(val);}});
            } else {
                map.get(key).add(val);
            }
            
            String rtKey = key+","+val;
            remainedTickets.put(rtKey, remainedTickets.getOrDefault(rtKey, 0) + 1);            
        }

        dfs("ICN", "ICN", 0);
        Collections.sort(result);
        answer = result.get(0).split(",");
        
        return answer;
    }
    
    public void dfs(String from, String path, int cnt){
        if(cnt == pathCnt){
            result.add(path);
            return;
        }
        if(map.get(from) == null) return;
        for(String to : map.get(from)){
            if(!canVisit(from, to)) continue;
            doVisit(from, to);
            dfs(to, path+","+to, cnt+1);
            cancelVisit(from, to);
        }   
    }
   
    public boolean canVisit(String from, String to){
        String key = from+","+to;
        if(remainedTickets.get(key) > 0) return true;
        return false;
    }
    
    public void cancelVisit(String from, String to){
        String key = from+","+to;
        remainedTickets.put(key, remainedTickets.get(key)+1);
    }
    
    public void doVisit(String from, String to){
        String key = from+","+to;
        remainedTickets.put(key, remainedTickets.get(key)-1);
    }
}