[프로그래머스][Lv3][Java] 여행경로

문제

[DFS]

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

프로그래머스

 

해설

• 깊이 우선 탐색(DFS)를 이용하여 주어진 티켓들로 구성된 여행 경로를 찾는 문제 해결 
• 주어진 티켓을 모두 사용하면서 사전 순으로 가장 빠른 경로를 찾는 것이 문제의 목표 

import java.util.*;

class Solution {
    
    public Queue<String> result = new PriorityQueue<>(); // 우선순위 큐를 이용하여 알파벳 순서대로 경로를 저장하는 큐
    public int[] visited; // 티켓을 사용했는지 여부를 저장하는 배열
    
    public String[] solution(String[][] tickets) {
        visited = new int[tickets.length]; 
        dfs("ICN", "ICN", tickets, 0); // DFS 탐색 시작
        String[] answer = result.peek().split(" "); // 결과 큐에서 가장 먼저 나온 경로를 가져와서 문자열 배열로 변환
        return answer;
    }
    
    private void dfs(String start, String route, String[][] tickets, int count) {
        if (count == tickets.length) { // 모든 티켓을 사용한 경우
            result.add(route); // 현재 경로를 큐에 추가
            return; 
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (visited[i] == 0 && tickets[i][0].equals(start)) { // 사용하지 않은 티켓이면서 출발지가 현재 위치와 일치하는 경우
                visited[i] = 1; // 티켓을 사용했다고 표시
                dfs(tickets[i][1], route + " " + tickets[i][1], tickets, count + 1); // 다음 단계의 DFS 호출
                visited[i] = 0; // 백트래킹: 다른 경로를 탐색하기 위해 티켓 사용 여부를 초기화
            }
        }
    }
}

1. 깊이 우선 탐색을 수행하는 재귀 메서드 사용 (dfs)
   
   1. start : 현재 위치, route : 현재까지의 경로, count : 사용한 티켓의 수, tickes : 전체 티켓 배열 
   2. 종료 시점 : 모든 티켓을 사용한 경우 현재 경로를 queue에 추가하고 종료
   3. 사용하지 않은 티켓이면서 출발지가 현재 위치와 일치할 경우 해당 티켓을 사용했다고 표시하고, 다음 단계의 DFS 호출
   4. 호출 시, 다음 출발지(tickets[i][1])와 경로에 추가된 부분을 업데이트
   5. 다음 DFS 호출이 끝나면 백트래킹을 수행하여 해당 티켓의 사용 여부를 초기화
2. result : 우선순위 큐를 사용하여 알파벳 순서대로 경로를 저장