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

문제

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

프로그래머스

 

---

 

문제 개요

이 문제는 주어진 항공권을 모두 사용해 여행 경로를 찾는 문제입니다. 여행은 항상 "ICN" 공항에서 출발하며, 항공권을 사용해 여러 공항을 방문하는 단 하나의 경로를 찾아야 합니다. 여행 경로를 찾는 것을 목표로 하며, 알파벳 순서에 따라 경로를 정렬하는 정렬 문제이기도 합니다.

문제 분석

1. 항공권 사용 조건: 모든 항공권을 반드시 사용해야 합니다.
2. 중복 경로: 여러 경로가 가능한 경우 알파벳 순서가 우선인 경로를 반환해야 합니다.
3. 탐색 방식: 각 항공권을 탐색해 조건을 만족하는 경로를 찾기 위해 DFS(깊이 우선 탐색)를 사용하며, 경로가 가능한지 확인하는 백트래킹 기법을 활용합니다.

문제 해결 방법

1. DFS와 백트래킹을 통해 경로를 탐색합니다.
2. 모든 항공권을 사용해야 하므로 항공권을 다 사용했을 때 완성된 경로를 저장합니다.
3. 여러 경로가 있을 수 있으므로 알파벳 순서로 정렬한 후, 가장 첫 번째 경로를 반환합니다.

 

import java.util.*;

class Solution {
    static List<String> list = new ArrayList<>();
    static boolean[] v;

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        // 방문 체크 배열 초기화
        v = new boolean[tickets.length];
        
        // DFS 탐색 시작
        dfs(tickets, "ICN", "ICN", 0);
        
        // 사전 순으로 정렬된 첫 번째 경로 반환
        Collections.sort(list);
        return list.get(0).split(" ");
    }
    
    public void dfs(String[][] tickets, String cur, String ans, int depth) {
        // 모든 항공권 사용 시 경로 저장
        if (depth == tickets.length) {
            list.add(ans);
            return;
        }
        
        // 항공권 탐색
        for (int i = 0; i < tickets.length; i++) {
            // 방문하지 않은 항공권 중 현재 공항 출발 항공권 탐색
            if (!v[i] && cur.equals(tickets[i][0])) {
                v[i] = true;
                dfs(tickets, tickets[i][1], ans + " " + tickets[i][1], depth + 1);
                v[i] = false;  // 백트래킹
            }
        }
    }
}