1. 문제 설명

여행경로

2. 문제 분석

연결 그래프를 만들고, 해당 간선을 모두 사용하는 경로 중 특정한 하나(가장 알파벳 순서대로 정렬된 경로)를 리턴하는 문제다.

• 문자열 형식의 티켓이기 때문에 해시 가능하도록 딕셔너리로 정리했고, 중복 티켓을 대비해서 각 티켓의 인덱스 값을 정수 배열로 간직하는 딕셔너리를 하나 더 만들었다.
• DFS를 통해 알파벳 순서대로 정렬된 일련의 티켓들을 먼저 돌기 때문에 가장 먼저 모든 도시를 여행 가능한 경로가 리턴되면 곧바로 답을 만들도록 했다.

3. 나의 풀이

import Foundation

struct Ticket: Hashable {
    let start: String
    let end: String
    
    init(_ start: String, _ end: String) {
        self.start = start
        self.end = end
    }
}

func solution(_ tickets:[[String]]) -> [String] {
    var ticketDict = [Ticket: [Int]]()
    var nodeDict = [String:[String]]()
    let ticketCnt = tickets.count
    var checked = Array(repeating: false, count: ticketCnt)
    var result = [String]()
    
    for item in tickets.enumerated() {
        let idx = item.offset
        let element = item.element
        let (start, end) = (element[0], element[1])
        let nodeValue = nodeDict[start] ?? []
        nodeDict[start] = nodeValue + [end]
        let ticketValue = ticketDict[Ticket(start, end)] ?? []
        ticketDict[Ticket(start, end)] = ticketValue + [idx]
    }
    
    for key in nodeDict.keys {
        var value = nodeDict[key] ?? []
        value.sort(by: <)
        nodeDict[key] = value
    }
    
    func DFS(_ curNode: String, _ path: [String]) {
        if path.count == ticketCnt + 1 {
            if result.isEmpty {
                result = path
            }
            return
        }
        
        let nextNodes = nodeDict[curNode] ?? []
        for nextNode in nextNodes {
            let nextIndices = ticketDict[Ticket(curNode, nextNode)] ?? []
            for nextIdx in nextIndices {
                if !checked[nextIdx] {
                    checked[nextIdx] = true
                    DFS(nextNode, path + [nextNode])
                    checked[nextIdx] = false
                }
            }
        }
    }
    
    let firstNode = "ICN"
    let secondNodes = nodeDict[firstNode] ?? []
    for secondNode in secondNodes {
        let nextIndices = ticketDict[Ticket(firstNode, secondNode)] ?? []
        for nextIdx in nextIndices {
            checked[nextIdx] = true
            DFS(secondNode, [firstNode, secondNode])
            if !result.isEmpty {
                return result
            }
            checked[nextIdx] = false
        }
    }
    
    return result
}