프로그래머스 여행경로 문제 (Swift 풀이)

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

프로그래머스

 

풀이 코드

import Foundation
 
func solution(_ tickets:[[String]]) -> [String] {
    var place: [String] = []
    var result: [String] = []
    
    tickets.forEach { ticket in
        if !place.contains(where: { $0 == ticket[0] }) {
            place.append(ticket[0])
        }
        if !place.contains(where: { $0 == ticket[1] }) {
            place.append(ticket[1])
        }
    }
    
    var ticket: [[Int]] = Array(repeating: Array(repeating: 0, count: place.count), count: place.count)
    
    place = place.sorted(by: <)
 
    tickets.forEach {
        let i = place.firstIndex(of: $0[0])!
        let j = place.firstIndex(of: $0[1])!
        ticket[i][j] += 1
    }
 
    var temp = dfs(place: place, ticket: ticket, path: [], targetLevel: tickets.count)
    for i in 0 ... temp.count - 1 {
        result.append(place[temp[i].0])
    }
    result.append(place[temp[temp.count - 1].1])
 
    return result
}
 
func dfs(place: [String], ticket: [[Int]], path: [(Int,Int)], targetLevel: Int) -> [(Int,Int)] {
    
    if path.isEmpty {
        let t = place.firstIndex(of: "ICN")!
        for (index, value) in ticket[t].enumerated() {
            if value > 0 {
                var ticket = ticket
                ticket[t][index] -= 1
                let result = dfs(place: place, ticket: ticket, path: [(t, index)], targetLevel: targetLevel)
                if result[0] != (-1,-1) {
                    return result
                }
            }
        }
    } else {
        let k = path.last!
        for (index, value) in ticket[k.1].enumerated() {
            if value > 0 {
                var ticket = ticket
                ticket[k.1][index] -= 1
                var path = path
                path.append(contentsOf: [(k.1, index)])
                
                if path.count == targetLevel {
                    return path
                } else {
                    let result = dfs(place: place, ticket: ticket, path: path, targetLevel: targetLevel)
                    if result[0] != (-1,-1) {
                        return result
                    }
                }
            }
        }
    }
    
    return [(-1,-1)]
}

 

풀이 과정

문제 조건에 알파벳 순서로 이른 순서의 항공권을 먼저 사용한다는 조건이 까다롭다.

문제 조건을 반영하여 DFS알고리즘으로 매 단계마다 다음 노드를 탐색할때 알파벳 순으로 탐색을 진행하도록 설계해야한다.

DFS 알고리즘은 가장 깊은 단계까지 먼저 탐색을하게되는데 매 단계에서 알파벳 순서를 고려하여 탐색을 진행한다면 가장 먼저 모든 항공권을 사용하는 단계까지 이른 탐색 경로가 정답이 된다.

 

우선, 주어진 모든 지역들을 place변수에 담은 뒤 알파벳 순으로 정렬을 진행한다.

그런 다음 정렬된 place가 목차가 되도록 ticket 행렬에 항공권들을 새로 담았다.

이제 ticket 행렬은 항공권들이 알파벳순으로 정렬되어 있으므로 dfs함수에선 배열의 순서대로 탐색을 진행하면 된다.

문제에 "중복되는 항공권은 없다"라는 언급이 없으므로 항공권이 중복되는 경우를 고려하여 true/false가 아닌 항공권의 개수를 ticket 행렬에 담는것이 중요하다.

 

배운 점

DFS 알고리즘 + 재귀함수의 설계 연습에 도움이 되었다.

특히 일반적인 탐색 문제에선 종단 노드까지 도달하지 못하게 되는 경우가 잘 없으므로 이 경우를 많이 놓치고 공부하고 있었는데,

이 문제의 경우 중간에 경로가 끊겼을때를 알 수 있는 장치 ( return [(-1,-1)] )를 추가하는 기법을 연습할 수 있었다.