99클럽 코테 스터디 34일차 TIL + 여행경로 (DFS, 백트래킹)

 

 

 

 

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

 

문제 & 키워드

• 프로그래머스 - 여행경로 (문제 링크)
• DFS (깊이 우선 탐색)
• 백트래킹

 

---

 

 

문제 설명

여행을 계획하는데 주어진 항공권을 모두 사용해야 하며, 모든 경로는 "ICN" 공항에서 시작해야 합니다. 항공권의 정보는 [출발지, 도착지]로 이루어진 2차원 배열 tickets로 주어집니다. 이때 가능한 여행 경로 중 알파벳 순서가 가장 앞서는 경로를 찾아 반환하는 문제입니다.

 

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 반환합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

입출력 예

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"]

 

 

---

 

 

문제 접근

1. 문제 이해
   • 이 문제는 주어진 항공권을 모두 사용하여 가능한 모든 경로를 찾고, 그 중 알파벳 순서가 가장 앞서는 경로를 반환해야 합니다.
   • DFS를 통해 각 항공권을 사용하여 도착 공항으로 이동하는 모든 가능한 경로를 탐색합니다. 이 과정에서 가능한 경로가 여러 개일 수 있기 때문에 백트래킹을 통해 모든 경로를 탐색하고 결과를 정렬하여 최종 경로를 반환해야 합니다.
2. 풀이 방법
   • DFS(깊이 우선 탐색)를 사용하여 각 공항에서 다음 공항으로 이동할 수 있는 모든 경로를 탐색합니다. 경로 탐색 중, 항공권을 모두 사용했을 때 현재 경로를 결과 리스트에 저장합니다.
   • 백트래킹을 사용하여 탐색을 완료한 후 다시 돌아가면서 다른 경로를 탐색합니다.
   • 모든 가능한 경로를 찾은 후, 결과를 알파벳 순서대로 정렬하여 최종 경로를 반환합니다.

 

 

풀이 - Java 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public String[] solution(String[][] tickets) {
        List<String> result = new ArrayList<>();
        boolean[] visited = new boolean[tickets.length];

        DFS(tickets, "ICN", "ICN", 0, result, visited);

        Collections.sort(result);

        return result.get(0).split(",");
    }

    private void DFS(String[][] tickets, String start, String sum, int depth, List<String> result, boolean[] visited) {
        if (depth == tickets.length) {
            result.add(sum);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            String left = tickets[i][0];
            String right = tickets[i][1];
            if (left.equals(start) && !visited[i]) {
                visited[i] = true;
                DFS(tickets, right, sum + "," + right,depth + 1,result,visited);
                visited[i] = false;
            }
        }
    }
}

풀이 설명

1. 초기화
   • tickets 배열에서 각 항공권 정보를 DFS를 통해 탐색하기 위해 필요한 변수들을 초기화합니다. 시작 공항인 "ICN"에서 출발하는 첫 번째 DFS 탐색을 시작합니다.
2. DFS 탐색
   • DFS는 현재 위치에서 출발 가능한 모든 항공권을 탐색합니다. 다음 공항으로 이동할 때, 해당 항공권을 사용한 것으로 표시(visited[i] = true)하고, 도착 공항으로 이동합니다.
   • 모든 항공권을 사용한 경우에는 현재까지의 경로를 결과 리스트에 추가합니다.
   • 탐색을 마친 후에는 다시 돌아와서 다른 가능한 경로를 탐색할 수 있도록 백트래킹으로 방문 상태를 복원합니다(visited[i] = false).
3. 결과 정렬
   • 모든 가능한 경로를 탐색한 후, 결과 리스트를 알파벳 순으로 정렬하여 가장 앞서는 경로를 선택합니다.
4. 결과 반환
   • 선택된 경로를 배열로 반환합니다.

 

 

---

 

 

마무리하며

• 이번 문제는 DFS와 백트래킹을 활용하여 가능한 모든 경로를 탐색하고, 사전순으로 가장 앞서는 경로를 찾는 문제였습니다.
• 다양한 경우의 수를 고려하여 탐색을 수행하고, 백트래킹을 통해 최적의 결과를 도출하는 경로 탐색 문제를 효과적으로 해결할 수 있었습니다.