[Level 3 / DFS] 여행경로 + Swift

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43164?language=swift

입력

let tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]

출력

["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

문제 풀이

1. solution 함수

dfs로 풀었다. 방문한 위치와 사용한 티켓을 저장하기 위해 places와 indexes라는 배열에 넣어(스택) 값을 저장하였다. 각 티켓을 정확히 한번만 사용한다. 티켓 모두를 사용할 수 있는 방법들을 다 구한 후 그 중에서 오름차순인 것을 고른다.

1. 정답을 저장할 results 배열을 변수로 생성한다.
2. dfs함수를 생성한다. dfs함수는 방문한 장소(공항)를 담는 places와 사용한 인덱스를 저장하는 indexes를 가진다.
3. 인덱스 개수가 티켓의 개수보다 크거나 같다면 results에 추가하고 함수를 나온다.
4. 현재 위치(places의 마지막 장소)가 티켓의 출발점(ticket[0])과 같고 티켓을 사용한 적이 없다면(해당 티켓의 인덱스가 인덱스 배열에 존재하지 않는다면) dict에 '인덱스: 다음 방문할 공항 이름' 형태로 추가한다.
5. dict의 각각의 요소에 대해서 dfs를 다시 실행한다.

*작성시 주의한 점

• 처음 "ICN"을 방문하므로, 값을 넣고 dfs 함수를 실행하였다. 그래서 places.last가 오류가 나지 않는다.
• 티켓의 인덱스와 다음 방문할 공항 이름 정보만 필요하기에 dict에 인덱스: 이름 형태로 저장하였다. 이중배열을 써도 괜찮다.

func solution(_ tickets: [[String]]) -> [String] {
    var results: [[String]] = []
    
    func dfs(_ places: [String] , _ indexes: [Int]) {
        var dict: [Int: String] = [:] // index: place
        
        if indexes.count >= tickets.count {
            results.append(places)
            return
        }
        
        for (index, ticket) in tickets.enumerated() {
            if (ticket[0] == places.last) && !indexes.contains(index) {
                dict[index] = ticket[1]
            }
        }
        
        dict.forEach({
            dfs(places + [$0.value], indexes + [$0.key])
        })
    }
    
    dfs(["ICN"], [])
    
    return results.sorted(by: sortByArrayElements)[0]
}

2. 두 배열을 비교하는 함수

results의 각 배열의 요소들을 확인해 알파벳 오름차순으로 정렬하고 싶었다. 문제에서 모든 공항은 알파벳 대문자 3글자로 이루어진다고 했으므로, 배열 내부의 문자열들을 합친 이후에 알파벳순으로 정렬해주는 sortByArrayElements함수를 구현하였다.

let results = [["a", "c"], ["a", "b"]]

print(arr.sorted(by: sortByArrayElements)) // [["a", "b"], ["a", "c"]]

func sortByArrayElements(_ lhs: [String], _ rhs: [String]) -> Bool {
    lhs.reduce("", +) < rhs.reduce("", +)
}