프로그래머스: 여행경로

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

프로그래머스

설명

나의 처음 아이디어는 map을 이용해서 푸는 것이었다.

key가 출발지가 되고, value는 도착지를 정렬해서 담고 있는 PriorityQueue이다.

그리고 매번 이동할 때마다, map에서 출발지를 찾고 도착지의 첫번째 원소가 이 다음 출발지가 되는 방식이다.

이런식으로 했을 때, 주어진 테스트 케이스는 통과되지만 다음 케이스같은 경우는 런타임에러가 발생한다.

• Parameters: [["ICN", "JFK"], ["ICN", "AAD"], ["JFK", "ICN"]]
• Return: ["ICN", "JFK", "ICN", "AAD"]

=> 출발지가 ICN일 때, PriorityQueue에 의해 정렬되어 AAD로 바로 방문할 수 있지만, AAD 이후에는 갈 곳이 없다...

=> 따라서 RuntimeError가 발생한다!

 

그럼 무슨 방법이 있을까? 

그렇다 탐색이다...

dfs로 갈 수 있는 경로를 구하고, 구한 경로들을 PriorityQueue에 넣는다.

경로들은 사전순으로 정렬되기 때문에 문제에서 요구하는 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 조건도 만족하게 된다.

 

코드

import java.util.*;

class Solution {
    static boolean[] visited;
    static PriorityQueue<String> queue;
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        queue = new PriorityQueue<String>();

        visited = new boolean[tickets.length];

        dfs("ICN", 0, "ICN", tickets);

        String stringAnswer = queue.poll();
        answer = stringAnswer.split(",");

        return answer;
    }

    static void dfs(String now, int count, String trip, String[][] tickets) {
        if(count == tickets.length) {
            queue.add(trip);
            return;
        }

        for(int i = 0; i < tickets.length; i++) {
            if(!visited[i] && now.equals(tickets[i][0])) {
                visited[i] = true;
                dfs(tickets[i][1], count+1, trip + "," + tickets[i][1], tickets);
                visited[i] = false;
            }
        }
    }
}