[코딩테스트] Java 여행경로

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

모든 항공권을 사용해 가능한 여행 경로를 찾고, 사전순으로 가장 앞선 경로를 반환합니다.

소스코드

import java.util.*;

class Solution {
    int n;
    boolean[] visited;
    ArrayList<String> arr = new ArrayList<>();
    
    public void dfs(int cnt, String start, String path, String[][] tickets) {
        if(cnt == n) {
            arr.add(path);
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if (!visited[i] && tickets[i][0].equals(start)) {
                visited[i] = true;
                dfs(cnt+1, tickets[i][1], path + " " + tickets[i][1], tickets);
                visited[i] = false;
            }
        }
    }
    
    public String[] solution(String[][] tickets) {
        n = tickets.length;
        visited = new boolean[n+1];
        
        dfs(0, "ICN", "ICN", tickets);
        
        Collections.sort(arr);

        return arr.get(0).split(" ");
    }
}

코드 설명

• 전역변수 초기화
  • int n;
    항공권의 개수입니다.
  • boolean[] visited;
    항공권이 이미 사용되었는지 여부를 기록하는 배열입니다.
  • ArrayList<String> arr = new ArrayList<>();
    가능한 모든 경로를 저장하는 리스트입니다.

public void dfs(int cnt, String start, String path, String[][] tickets) {
    if(cnt == n) {
        arr.add(path);
        return;
    }

    for(int i = 0; i < n; i++) {
        if (!visited[i] && tickets[i][0].equals(start)) {
            visited[i] = true;
            dfs(cnt+1, tickets[i][1], path + " " + tickets[i][1], tickets);
            visited[i] = false;
        }
    }
}

• dfs 메소드
  • cnt == n이면 모든 항공권을 사용한 경로가 완성된 상태입니다.
  • 현재 위치 start와 일치하는 출발지를 가진 항공권을 찾습니다. 아직 사용되지 않은 항공권(!visited[i])만 선택합니다.
  • 선택한 항공권을 사용(visited[i] = true)하고, 목적지(tickets[i][1])로 이동합니다.
  • 재귀 호출이 끝난 후, 현재 항공권 사용 상태를 복구(visited[i] = false)하여 다른 경로를 탐색할 수 있도록 합니다.

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

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

    Collections.sort(arr);

    return arr.get(0).split(" ");
}

• solution 메소드
  • 탐색을 시작하기 위해 dfs(0, "ICN", "ICN", tickets)를 호출합니다.
  • Collections.sort(arr)로 모든 경로를 사전순으로 정렬합니다.