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

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

프로그래머스

 

첫 번째 풀이는 String을 사용

import java.util.*;
 
class Solution {
    
    static int depth = 0;
    static boolean[] visited;
    static ArrayList<String> answer = new ArrayList<>();
    
 
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length]; // 티겟 개수만큼만 방문
        dfs(depth, "ICN", "ICN", tickets);
        Collections.sort(answer);
        String[] path = answer.get(0).split(" ");
        return path;
    }
    
    public void dfs(int depth, String now, String path, String[][] tickets){
        if (depth == tickets.length){
            answer.add(path);
            return;
        }
        for (int i = 0; i<tickets.length; i++){
            if(!visited[i] && tickets[i][0].equals(now)){
                visited[i] = true;
                dfs(depth+1, tickets[i][1], path+" "+tickets[i][1], tickets);
                visited[i] = false;
            }
        }
        return;
    }
}

시간이 오래 나와 리팩토링을 하였고, StringBuilder를 사용함

import java.util.ArrayList;
import java.util.Collections;
 
class Solution {
    static ArrayList<String> answer = new ArrayList<>();
    static boolean[] visited;
    static int depth = 0;
 
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length]; // 티켓 개수만큼 방문 여부를 저장하는 배열 초기화
        dfs(depth, "ICN", new StringBuilder("ICN"), tickets); // DFS 탐색 시작
        Collections.sort(answer); // 경로를 사전순으로 정렬
        String[] path = answer.get(0).split(" "); // 첫 번째 경로를 공백을 기준으로 분할하여 배열로 반환
        return path; // 최종 경로 반환
    }
 
    private void dfs(int depth, String now, StringBuilder path, String[][] tickets) {
        if (depth == tickets.length) { // 모든 티켓을 사용한 경우
            answer.add(path.toString()); // 경로를 정답 리스트에 추가
            return;
        }
 
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(now)) { // 방문하지 않았고 출발지가 현재 위치와 일치하는 티켓인 경우
                visited[i] = true; // 해당 티켓을 사용함으로 처리
                path.append(" ").append(tickets[i][1]); // 경로에 도착지 추가
                dfs(depth + 1, tickets[i][1], path, tickets); // 재귀 호출
                path.delete(path.length() - 4, path.length()); // 경로에서 추가했던 도착지 제거 (공백과 도착지 3글자)
                visited[i] = false; // 재귀 호출이 끝나면 다른 경로를 찾기 위해 해당 티켓을 다시 방문하지 않은 상태로 처리
            }
        }
    }
}
 

 

코드 풀이
1. `DFS` 메서드는 깊이 우선 탐색을 수행하는 재귀 함수입니다. 이 함수는 현재 위치(`now`), 경로 정보(`path`), 방문 상태(`visited`), 티켓 정보(`tickets`)를 인자로 받습니다.
2. `depth` 변수는 현재까지 진행한 경로의 길이를 나타내며, 초기 값은 0입니다.
3. 첫 번째 호출 시에는 출발지인 "ICN"을 시작으로 경로(`path`)를 "ICN"으로 초기화합니다.
4. 재귀 호출이 시작되면 현재 위치(`now`)와 경로(`path`)를 갱신합니다.
5. `depth`와 티켓의 길이가 같다면 모든 티켓을 사용한 경로를 찾은 것이므로, 해당 경로를 `answer` 리스트에 추가하고 함수를 종료합니다.
6. 티켓을 순회하며 사용하지 않은 티켓 중에서 현재 위치와 일치하는 티켓을 찾습니다.
7. 해당 티켓을 사용한 경우, 방문 상태를 업데이트하고 경로에 도착지를 추가합니다.
8. 재귀 호출을 통해 다음 위치로 이동합니다. `depth`를 1 증가시키고, 도착지를 현재 위치로 설정하고, 갱신된 경로와 업데이트된 방문 상태를 전달합니다.
9. 재귀 호출이 끝난 후에는 다른 경로를 탐색하기 위해 방문 상태와 경로 정보를 원래 상태로 복구합니다.
10. `path`의 마지막에 추가된 도착지를 제거합니다.
11. 티켓을 순회하며 다른 경로를 탐색합니다.
12. 모든 경로 탐색이 완료되면 `answer` 리스트에 저장된 경로들을 정렬합니다.
13. 가장 먼저 나오는 경로를 선택하여 공백을 기준으로 나누어 문자열 배열로 반환합니다.

이 알고리즘은 주어진 티켓을 모두 사용하며 가능한 모든 경로를 탐색하는 것을 목표로 합니다. DFS를 사용하는 이유는 출발지부터 도착지까지 연속적으로 탐색하면서 가능한 경로를 찾을 수 있기 때문입니다. DFS는 스택 자료구조를 활용하며 깊이 우선 탐색을 수행합니다. 이를 통해 모든 가능한 경로를 탐색하고, 그 중 가장 빠른 경로를 선택하여 반환합니다.