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

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

프로그래머스

 

문제 풀이

이 문제의 경우 그래프로 풀 수 있는데 평소 트리나 그래프의 경우 노드의 방문여부를 체크했다면 이 문제는 간선의 방문 여부를 체크해야 한다. 왜냐면 A->B로 가도 B->A가 있다면 A가 다시 방문될 수 있고 해당 문제에서 모든 tickets을 사용해야 하기 때문에 모든 간선을 사용해야 한다는 뜻이다.

tickets을 간선으로 생각하고 visited를 tickets 갯수만큼 생성하였고 dfs의 cnt를 두어 tickets의 갯수, 즉 조건에 맞는 모든 간선을 체크하였을 때 방문한 모든 String을 List의 answer에 저장해 둔다.

List를 사용한 이유는 다음과 같이 알파벳 순으로 정렬해야 하기 때문이다.

예제 #2
["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만
["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

 

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    static boolean visited[];
    static List<String> answer = new ArrayList<>();
    static String[][] tickets;

    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        this.tickets = tickets;

        dfs("ICN", "ICN", 0);
        answer.sort(Comparator.naturalOrder());
        return answer.get(0).split(" ");
    }

    static void dfs(String start, String route, int cnt){
        if (cnt == tickets.length) {
            answer.add(route);
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals(start) && !visited[i]){
                visited[i] = true;
                dfs(tickets[i][1], route + " " + tickets[i][1], cnt + 1);
                visited[i] = false;
            }
        }
    }
}