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

(문제 설명)

 

(제한 사항)

DFS(깊이 우선 탐색) 알고리즘을 구현하여 해결하는 문제이다.

코드를 다 짜고 나니깐, 굳이 map으로 하지 않고 Arraylist를 사용해도 됐다는 것을 깨달았다.

 

 

알고리즘 구현 방법

 1. tickets 배열 정렬

 2. "ICN"을 시작으로, 연결할 수 있는 티켓(ticket[n][1]) map에 넣기 

    ** map의 key는 인덱스, value는 ticket[n][1]을 저장함.

 3. map의 크기가 tickets.length+1 이 안된다면 백트래킹

        (2, 3번 반복)

 4. answer 배열에 넣기

 

public static void main(String[] args) throws ParseException {
    String[][] tickets= {{"ICN","B"},{"B","ICN"},{"ICN","A"},{"A","D"},{"D","A"}};
    
    // tickets 정렬
    Arrays.sort(tickets, new Comparator<String[]>() {
        @Override
        public int compare(String[] o1, String[] o2) {
            if(o1[0].toString().contentEquals(o2[0].toString()))
                return o1[1].toString().compareTo(o2[1].toString());
            else
                return o1[0].toString().compareTo(o2[0].toString());
            }			
    });

    LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
    map.put(tickets.length, "ICN");	// 출발지 ICN 입력
        
    dfs(tickets, map, 1);
        
    String[] answer = new String[map.size()];
    int num = 0;
    for(Integer i: map.keySet())
        answer[num++] = map.get(i);
		
    System.out.println(Arrays.asList(answer));
}
	
public static LinkedHashMap<Integer, String> dfs(String[][] tickets, LinkedHashMap<Integer, String> map, int key) {
    Integer[] tmp = new Integer[map.size()];
    map.keySet().toArray(tmp);
		
    int ex = tmp[tmp.length-1];    // 이전에 입력한 티켓 인덱스 ex 변수에 저장
    StringBuilder str = new StringBuilder(map.get(ex));    // 이전에 입력한 티켓 str 변수에 저장
        
    if(key == tickets.length+1) return map;    // key값이 (ticket 길이+1) 이라면 리턴

// key 값이 다르다면(작다면), 백트래킹한 것임
    if(key != map.size()) {
        map.remove(ex);
        str.delete(0, str.length());
        str.append(map.get(tmp[tmp.length-2]));
    }
		
    int i=0;
    while(map.size() < tickets.length+1) {        // map 채워넣는 while문
        if(map.size() == tickets.length+1) return map;
        if(i == tickets.length) {
            int flag = 0;
            for(int j=0; j<tickets.length; j++)
                if(tickets[j][0].equals(str.toString()) && !map.containsKey(j) && j!=ex) flag = 1; 

            if(flag == 1) i = 0;
            else return dfs(tickets, map, --key);         // 백트래킹
        }

    // 이전의 입력한 티켓이 tickets[i][0]과 같다면 map에 tickets[i][1] 넣음.
        if(i != ex && (str.toString()).equals(tickets[i][0]) && !map.containsKey(i)) {
            map.put(i, tickets[i][1]);
            return dfs(tickets, map, key+1);
        }
        i++;
    }
    return map;
}