[43164] 여행경로

✔ 여행경로

[프로그래머스 43164]

문제 분석하기

DFS를 수행하며 가능한 모든 경로를 문자열로 저장한 후 정렬을 하여 가능한 경로 중 알파벳 순서가 앞서는 경로를 찾도록 함

예) ["ICN", "SFO"], ["SFO", "ATL"]

"ICN" → "SFO" → "ATL"

손으로 풀어보기

1. 항공권들과 현재 항공권을 비교하여 다음 공항으로 갈 수 있다면 그 항공권을 사용
   • 이를 반복하여 모든 경로를 탐색할 때까지 반복
   • 이동할 때마다 사용한 항공권 수 증가
2. 모든 경로들을 정렬한 후 가장 앞의 경로를 출력

슈도코드 작성하기

tickets(항공권 정보가 담긴 2차원 배열)
answer(방문하는 공항 경로 배열)
allRoute(방문하는 모든 공항 경로 리스트)
visited(항공권 사용 유무 배열)
visitCount(사용한 항공권 수)
dfs("ICN", "ICN", ticktets, visitCount)
allRoute 정렬
answer = allRoute.get(0).split(" ")
answer 반환

dfs {
    if(모든 항공권을 사용했다면) {
        allRoute.add(route)
        return;
    }
    for(i -> tickets만큼) {
        if(tickets[i][0]이 항공권 출발지와 같으며 항공권 i를 사용하지 않았다면) {
            visited[i] = true
            dfs(tickets[i][1], route + " " + tickets[i][1], tickets, visitCount + 1)
            visited[i] = false
        }
    }
}

코드 구현하기

/**
 * 43164) 여행경로
 */
public class K004_43164 {
    static ArrayList<String> allRoute;
    static boolean[] visited;

    // tickets(항공권 정보가 담긴 2차원 배열)
    public String[] solution(String[][] tickets) {
        // answer(방문하는 공항 경로 배열)
        String[] answer = {};
        // allRoute(방문하는 모든 공항 경로 리스트)
        allRoute = new ArrayList<>();
        // visited(항공권 사용 유무 배열)
        visited = new boolean[tickets.length];
        // visitCount(사용한 항공권 수)
        int visitCount = 0;
        // 가능한 모든 경로 탐색
        dfs("ICN", "ICN", tickets, visitCount);
        // allRoute 정렬
        Collections.sort(allRoute);
        // " "으로 분리하여 저장
        answer = allRoute.get(0).split(" ");
        // answer 반환
        return answer;
    }

    private void dfs(String start, String route, String[][] tickets, int visitCount) {
        // 모든 항공권을 사용했다면
        if (visitCount == tickets.length) {
            // 현재 경로를 모든 공항 경로 리스트에 저장
            allRoute.add(route);
            return;
        }
        for (int i = 0; i < tickets.length; i++) {
            // tickets[i][0]이 항공권 출발지와 같으며 항공권 i를 사용하지 않았다면
            if (start.equals(tickets[i][0]) && visited[i] != true) {
                // 현재 항공권 사용 처리 갱신
                visited[i] = true;
                // 현재 항공권의 도착지를 출발지로 변경한 후 경로 탐색
                dfs(tickets[i][1], route + " " + tickets[i][1], tickets, visitCount + 1);
                // 현재 항공권 사용 초기화
                visited[i] = false;
            }
        }
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K004_43164 solution = new K004_43164();

        String[][] tickets = { { "ICN", "SFO" }, { "ICN", "ATL" }, { "SFO", "ATL" }, { "ATL", "ICN" },
                { "ATL", "SFO" } };

        String[] result = solution.solution(tickets);

        System.out.println(Arrays.toString(result));
    }
}