[프로그래머스] 여행 경로 | DFS, BFS | Level.3 | JAVA

📌 문제

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

프로그래머스

 

---

 

⭐ 알고리즘 선정 : DFS? or BFS?

이 문제는 DFS(Depth-First Search)로 해결하는 것이 적합합니다. 그 이유는 다음과 같습니다:

문제의 특징

1. 모든 항공권을 사용해야 한다: 주어진 항공권을 모두 이용하여 경로를 구성해야 하므로, 가능한 모든 경로를 탐색해야 합니다.
2. 경로의 알파벳 순서: 여러 경로 중 알파벳 순서가 가장 앞서는 경로를 선택해야 하므로, 깊이 탐색하면서 정렬된 경로를 유지해야 합니다.

DFS의 적합성

• 모든 경로 탐색: DFS는 깊이 있는 탐색을 통해 모든 가능한 경로를 고려할 수 있으므로, 주어진 항공권을 모두 사용한 경로를 찾는 데 유리합니다.
• 백트래킹: 이미 방문한 공항을 기록하고, 경로가 완료된 후에는 다시 되돌아가 다른 경로를 탐색할 수 있습니다.
• 알파벳 정렬: 경로를 탐색할 때, 항공권을 알파벳 순으로 정렬한 후 DFS를 적용하면, 자연스럽게 알파벳 순서가 앞서는 경로를 우선적으로 찾을 수 있습니다.

결론

따라서 이 문제는 DFS를 활용해 해결하는 것이 적합하며, 모든 항공권을 사용한 후 알파벳 순으로 정렬된 경로를 찾아야 합니다. BFS는 최단 경로를 찾는 데 적합하지만, 이 문제에서는 모든 경로를 탐색하는 것이 목표이므로 DFS를 선택해야 합니다.

 

---

 

🤔 생각할 것들

이 문제를 풀기 위해 두 가지가 고민이 되었습니다.

첫 번째로는, 각 공항을 어떻게 연결할 수 있을까.

두 번째는, 어떻게 알파벳 순으로 더 앞에 있는 것을 연결할 수 있을까.

였습니다.

첫 번째 고민은 문제에서 주어진 [출발지, 도착지]로 고정된 배열을 이용해서 도착지(맨 처음에는 출발지(=ICN), 그 다음부턴 도착지(=인덱스가 1일 때))가 출발지(인덱스가 0일 때)와 같을 때로 연결하면 해결이 됩니다.

두 번째 고민은 DFS 방식을 이용해서, 모든 경로를 모두 구해서 각 경로를 문자열에 답고, 이렇게 경로를 나타내는 문자열이 담긴 모든 경로를 가지고 있는 문자열 배열을 정렬합니다. 정렬한 후 가장 앞에 있는 경로가 알파벳 상으로 앞에 위치했다는 것이기 때문에 이를 출력하면 해결이 됩니다.

여기서 모든 경로를 구하기 위해 방문 배열을 false로 바꿔주어 다시 백트래킹해서 돌아왔을 때 다른 경로도 확인할 수 있게 해주었습니다.

 

#️⃣ 정답 코드

import java.util.*;

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

 

⭐ 코드 설명

✅ DFS 과정

[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]를 예시로 설명해드리겠습니다.

1. DFS를 재귀적으로 호출해가며 route로 ICN → ["ICN", "SFO"] →  ["SFO", "ATL"]  → ["ATL", "ICN"] →  ["ICN", "ATL"] →  ["ATL","SFO"] 가 선택되어집니다.

2. 백트래킹 :  visited[i] = false를 해나가며 다른 경로가 있는지 확인합니다. 백트래킹하다 다른 선택지가 나오는 순간은 맨처음인 ICN에서 SFO가 아닌 ATL을 선택하는 순간입니다. ATL도 두가지 경로가 있지만, 3번째에 ["ATL", "ICN"] 대신 ["ATL","SFO"]를 선택하면 SFO를 시작으로 하는 경로가 더 없기 때문에 맨처음인 ICN까지 백트래킹하게 됩니다.

3. 이번엔  ICN에서 ["ICN", "SFO"] 대신 ["ICN", "ATL"] 를 선택합니다. 그래서 route는 ICN → ["ICN", "ATL"] → ["ATL", "ICN"] → ["ICN", "SFO"] → ["SFO", "ATL"] → ["ATL","SFO"] 가 됩니다.

4. 백트래킹 : visited[i] = false를 해나가며 다른 경로가 있는지 확인합니다. 다른 선택지가 나오는 순간은, 두 번째에 ["ATL", "ICN"] 대신  ["ATL","SFO"] 를 선택하는 순간입니다.

5. route는 ICN → ["ICN", "ATL"] → ["ATL","SFO"] → ["SFO", "ATL"] →  ["ATL", "ICN"] → ["ICN", "SFO"] 가 됩니다.

6. count가 length와 같아질 때는 더 이상 백트래킹할 필요가 없는 상태를 나타냅니다. 그래서 dfs 함수가 종료되고 위처럼 3가지 경로가 list에 추가된 채로 끝납니다. 

count에 대한 설명은 아래에서 더 자세히 해드리겠습니다.

마지막으로 main 함수에서 정렬해서 첫번째 값을 출력해면 이게 결국엔 알파벳 순으로 더 앞인 최적의 경로를 출력할 수 있는 것입니다!

 

✅ dfs 종료조건 : count

count는 DFS의 탐색 깊이를 나타냅니다.

사실 그래서 count가 아닌 depth로 표현했으면 더 좋았을 거 같다는 생각이 지금 드네요!! 

사실 맨처음 코드를 작성할 때 count+1로 매개변수에 전달하지 않고 count++를 써서 전달했었는데요. 이러면 안되는 이유가 다시 백트래킹해서 돌아왔을 때 해당 count, 즉 깊이를 기억해야하기 때문입니다.

count++는 현재의 count 값을 사용한 후에 1을 증가시킵니다. 즉, DFS 탐색의 깊이를 정확히 반영하지 못합니다. 이 경우, DFS가 다음 단계로 진행되기 전에 count 값이 증가하지 않기 때문에, 재귀 호출에서 여전히 이전 상태의 count 값이 사용됩니다.

count + 1을 사용하면, 현재 사용 중인 티켓 수를 하나 증가시켜 다음 단계의 DFS에서 사용할 수 있도록 합니다. 이렇게 하면 현재 티켓을 사용한 상태가 올바르게 반영되어 DFS의 깊이를 정확하게 추적할 수 있습니다.

즉, 새로운 재귀 호출에서는 현재 사용한 티켓 수가 포함된 count가 전달되므로, 탐색 깊이를 제대로 표현하게 됩니다.

DFS는 재귀적으로 진행되며, 각 단계에서 탐색 깊이를 적절히 반영해야 합니다. 이 깊이를 정확하게 유지하지 않으면, count가 잘못된 값으로 평가되거나 기저 조건을 놓칠 수 있습니다.

count + 1을 사용함으로써, 매 호출마다 현재까지 사용한 티켓 수가 올바르게 증가하고, 이는 후속 탐색에 영향을 미치게 됩니다.

결국 모든 경로를 구한 상태에서는 count == length가 되어 for문을 빠져나오게 되는 것입니다. 

 

---

 

공부의 흔적