[프로그래머스/lv3] 여행경로

문제 정보

[프로그래머스/lv3] 여행경로

항공권의 경로를 input으로 받아, 모든 항공권을 사용하는 방법을 구하는 DFS 문제로, 목적지가 여러 곳이라면 알파벳 순서대로 가장 빠른 경로를 output으로 결정해야한다.

입출력 예

tickets	return
[[“ICN”, “JFK”], [“HND”, “IAD”], [“JFK”, “HND”]]	[“ICN”, “JFK”, “HND”, “IAD”]
[[“ICN”, “SFO”], [“ICN”, “ATL”], [“SFO”, “ATL”], [“ATL”, “ICN”], [“ATL”,”SFO”]]	[“ICN”, “ATL”, “ICN”, “SFO”, “ATL”, “SFO”]

풀이

해당 문제에서 가장 신경쓰였던 점은

만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

이 조건을 만족하기 위해 아래 2가지 방법을 생각했다.

1. 모든 탐색 경로를 조회하고 가장 알파벳 순으로 빠른 경로를 출력
2. tickets 자체를 정렬하고 가장 먼저 찾은 경로를 출력

처음 구현할 때는 1번의 방식으로 하였지만, 여러 개의 List를 사용하는 것에 overhead를 느끼고, tickets 자체를 정렬하면 첫 번째 DFS 탐색된 List가 정답임을 깨달아 2번의 방식으로 전환하였다.

2차원 배열을 사전순 정렬하는법

:: 방식이 조금 낯설게 느껴진다면 아래와 같이 람다식으로 풀어 쓰기도 가능하다.

// 티켓 정렬
Arrays.sort(tickets, Arrays::compare);
// Lamda로 
Arrays.sort(arr, (a, b) -> Arrays.compare(a, b));

DFS 사용

한번 정렬된 tickets 배열을 사용하기에 DFS 자체는 매우 정석적이다.

다만, 무조건 첫 탐색이 정답이기에 if를 통해 탐색이 완료 되었다면 return하는게 조금 다른 편.

  public boolean DFS(String[][] tickets, boolean[] visited, String[] answer, int depth, String stat) {
      // 첫번째 탐색이 정답
      if (depth > airportCount) 
          return true;

      for (int i = 0; i < airportCount; i++) {
          String dest = tickets[i][1];
          if (!visited[i] && stat.equals(tickets[i][0])) {
              visited[i] = true;
              answer[depth] = dest;
              if (DFS(tickets, visited, answer, depth + 1, dest))
                  return true; // 즉시 종료
              visited[i] = false;
          }
      }
      
      return false;
  }

2차원 배열의 정렬 방식을 숙지하고 있다면 매우 쉽게 느껴질 수 있었던 문제였다.

다만 해당 방식을 떠올리지 못했고, 다른 방식으로 한번 접근하면서 조금 헛발질을 많이 하였다.

전체 코드

class Solution {
    int airportCount = 0; // 공항의 전체 숫자
    public String[] solution(String[][] tickets) {
        // 초기 설정 (공항 갯수, 출발 공항 ICN)
        airportCount = tickets.length;
        String[] answer = new String[airportCount + 1];
        answer[0] = "ICN";
        
        // 티켓 정렬
        Arrays.sort(tickets, Arrays::compare);
        
        // DFS 탐색
        DFS(tickets, new boolean[airportCount], answer, 1, "ICN");
        
        return answer;
    }
    
    public boolean DFS(String[][] tickets, boolean[] visited, String[] answer, int depth, String stat) {
        // 첫번째 탐색이 정답
        if (depth > airportCount) 
            return true;

        for (int i = 0; i < airportCount; i++) {
            String dest = tickets[i][1];
            if (!visited[i] && stat.equals(tickets[i][0])) {
                visited[i] = true;
                answer[depth] = dest;
                if (DFS(tickets, visited, answer, depth + 1, dest))
                    return true; // 즉시 종료
                visited[i] = false;
            }
        }
        
        return false;
    }
}