[프로그래머스] Swift - 여행경로

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

프로그래머스

 

2023.07.19 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

주어진 tickets들이 모든 도시를 방문할 수 있다고 문제 조건이 있기 때문에 tickets들을 탐색하며 방문하는 공항 경로를 구하면 됩니다.

 

한 출발지에서 여러 도착지 공항으로 갈 수 있기 때문에 매번 반복문으로 tickets을 순회하지 않으려면 딕셔너리에 출발지와 도착지를 저장하는 것이 효과적일 것이라고 생각했습니다.

따라서 [출발지: [도착지들]] 형태의 딕셔너리를 생성하여 티켓 정보를 저장합니다.

 

그리고 ICN부터 시작해서 가능한 경로들을 탐색해야 하기 때문에 DFS를 활용합니다.

 

ICN이 출발지일 경우의 도착지들이 여러개 있을텐데 이 도착지들을 다시 출발지로 설정하여 다음 레벨(dfs함수 호출)로 넘어갑니다.

이때 한번 사용한 티켓을 중복으로 사용하지 않기 위해 visited 배열을 생성하여 사용한 티켓을 true로 지정합니다.

dfs 함수 실행이 완료되면 다시 false로 지정하여 해당 티켓을 사용 가능하도록 바꿉니다. 

 

풀이

fileprivate func solution(_ tickets:[[String]]) -> [String] {
    
    var dict = [String: [String]]() // key: 출발 공항, value: 도착 공항
    
    for ticket in tickets {
        dict[ticket[0], default: []].append(ticket[1])
    }
    
    var visited = [String: [Bool]]() // key: 출발 공항, value: 도착 공항을 방문한 적이 있는지 기록
    
    for key in dict.keys {
        dict[key]?.sort()
        visited[key] = Array(repeating: false, count: dict[key]!.count)
    }
    
    var result = [String]()
    
    func dfs(departure: String, now: [String]) {
        if !result.isEmpty {
            return
        }
        
        if now.count == tickets.count + 1 {
            result = now
            return
        }
        
        let arrivals = dict[departure, default: []]
        
        for (index, arrival) in arrivals.enumerated() {
            if visited[departure]![index] == false {
                visited[departure]![index] = true
                dfs(departure: arrival, now: now + [arrival])
                visited[departure]![index] = false
            }
        }
    }
    
    dfs(departure: "ICN", now: ["ICN"])
    
    return result
}

 

문제 조건에서 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return하라고 했기 때문에 dict의 value값들을 오름차순으로 정렬시켜서 항상 알파벳 순서가 앞서는 경로가 먼저 탐색되도록 했습니다.

 

dfs의 종료 조건은 result를 이미 찾은 경우와 now 배열 (답안 후보)의 길이가 tickets.count + 1인 경우입니다.

tickets의 개수가 3개이면 공항 경로 배열의 count는 4인 것처럼 result의 길이는 항상 tickets.count+1이기 때문입니다.

 

마무리

DFS 경로 탐색 문제였습니다.

7/19일 기준으로는 테스트 케이스가 많지 않아서 딕셔너리를 사용하지 않고 매번 반복문으로 찾아도 통과를 하는 것 같지만 그래도 코드를 좀 더 구조화해서 티켓 정보와 방문 기록을 저장하기 위해 딕셔너리를 활용했습니다.