[PG] 여행경로 JAVA

programmers.co.kr/learn/courses/30/lessons/43164

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

항공권의 배열 String[][] tickets 가 주어진다. (항공권은 [출발지, 도착지] 로 되어있다)

주어진 항공권을 모두 사용하는 여행경로를 담은 배열을 반환해야한다.

 

1. 맨 처음 시작은 ICN 에서만 한다.

2. 항공권을 모두 사용하는 경로가 여러 개일 경우 알파벳 순서가 빠른 것을 정답으로 한다.

3. 정답이 없는 경우는 없다.

 

 

 

풀이 .

import java.util.*;

class Solution {
    boolean[] check = null;
    String[] answer = null;
    ArrayList<String> temp = null;

    public void dfs(int dept, String now, String[][] tickets) {
        // dept == 방문한 장소 개수 == 다음 장소 입력할 인덱스
        if(dept == tickets.length + 1) {
            if(answer[0] == null) {
                answer = temp.toArray(new String[tickets.length + 1]);
                return;
            }

            for(int i = 0; i < tickets.length + 1; i++) {
                if(answer[i].compareTo(temp.get(i)) == 0) {
                    continue;
                }else if(answer[i].compareTo(temp.get(i)) < 0) {
                    return;
                }else if(answer[i].compareTo(temp.get(i)) > 0) {  // 새로운 정답이 더 빠르면 교체
                    answer = temp.toArray(new String[tickets.length + 1]);
                    return;
                }
            }
        }

        for(int i = 0; i < tickets.length; i++) {
            if(check[i] == false && now.equals(tickets[i][0])) {
                check[i] = true;
                temp.set(dept, tickets[i][1]);
                dfs(dept + 1, tickets[i][1], tickets);
                check[i] = false;
            }
        }
    }

    public String[] solution(String[][] tickets) {
        answer = new String[tickets.length + 1];
        check = new boolean[tickets.length];
        temp = new ArrayList<>();

        // add 없이 set 하면 에러남
        for(int i = 0; i < tickets.length + 1; i++) {
            temp.add("");
        }

        // ICN 에서만 출발 가능
        for(int i = 0; i < tickets.length; i++) {
            if(tickets[i][0].equals("ICN")) {
                check[i] = true;
                temp.set(0, tickets[i][0]);
                temp.set(1, tickets[i][1]);
                dfs(2, tickets[i][1], tickets);
                check[i] = false;
            }
        }

        return answer;
    }
}

 

'단어 변환' 문제와 거의 유사한 문제.

 

똑같이 DFS, 백트래킹을 사용해서 풀었다.

 

백트래킹 할 때 ArrayList에 집어넣었던 경로를 빼는 게 불편해서 스택으로 바꿀까 싶었지만 ArrayList.set() 으로 해결했다.

set() 을 사용하면 집어넣을 인덱스를 지정할 수 있기 때문에 굳이 remove() 를 하지 않아도 된다.