[프로그래머스/Java] Lv.3 - 여행경로

프로그래머스 Lv.3 - 여행경로

요구사항

• 주어진 항공권을 모두 사용해 방문하는 공항 경로를 구하는 문제
• 항상 ICN에서 출발
• 가능한 경로가 여러 개인 경우 알파벳 순서가 앞서는 경로를 반환

접근 방식

DFS + 백트래킹 으로 모든 티켓을 사용하는 경로를 탐색했다.

핵심 아이디어

• 티켓을 목적지 알파벳 순으로 정렬 → 자동으로 사전순 처리
• DFS로 경로 탐색, 모든 티켓 사용 완료(cnt == n)시 성공
• 막다른 길에서 백트래킹 으로 되돌아가서 다른 경로 시도

백트래킹이 필요한 이유

ICN → BBB
ICN → AAA
BBB → ICN

알파벳순으로 ICN → AAA 선택시 막힘!
→ 백트래킹으로 되돌아가 ICN → BBB → ICN → AAA 선택

알파벳순 정렬만으로는 항상 모든 티켓 사용이 보장되지 않는다.
막다른 길이 생길 수 있으므로 반드시 백트래킹이 필요하다.

코드

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        Arrays.sort(tickets, (a, b) -> a[1].compareTo(b[1]));
        int n = tickets.length;

        boolean[] visit = new boolean[n];
        ArrayList<String> al = new ArrayList<>();
        al.add("ICN");

        dfs(0, n, "ICN", tickets, visit, al);

        return al.stream().toArray(String[]::new);
    }

    public boolean dfs(int cnt, int n, String now, String[][] tickets,
                       boolean[] visit, ArrayList<String> al) {
        if (cnt == n) return true;

        for (int i = 0; i < n; i++) {
            if (visit[i]) continue;
            if (tickets[i][0].equals(now)) {
                visit[i] = true;
                al.add(tickets[i][1]);
                if (dfs(cnt+1, n, tickets[i][1], tickets, visit, al)) return true;
                // 백트래킹
                visit[i] = false;
                al.remove(al.size()-1);
            }
        }
        return false;
    }
}

느낀점

• 처음에 알파벳순 정렬만 하면 순서대로 따라가면 된다고 생각했는데,
  알파벳순으로 가다가 막히는 경우가 생길 수 있어서 백트래킹이 반드시 필요하다.
• 백트래킹은 visit = false, al.remove() 로 방문 처리와 경로를 되돌리는 것이 핵심이다.
• ICN 시작도 DFS 안에서 처리해야 백트래킹 대상에 포함된다.