[Swift/프로그래머스] 여행경로 ( DFS , 딕셔너리 )

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

프로그래머스

 

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

방문처리를 Set으로 하니 중복 문자열은 방문하지 않고 끝나는 문제가 발생했다.

 

첫 풀이

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    
    // 알파벳 순으로 앞선 결과를 원하기때문애 이렇게 정렬
    let sortedTickets = tickets.sorted{
        $0[1] < $1[1]
    }
    
    // DFS를 사용하면 된다. queue가 아닌 Stack
    // [:] String [String] 하면되지않을까. 
    var target = [String: [String]]()
    for ticket in sortedTickets {
        target[ticket[0],default:[]].append(ticket[1])
    }
    
    
    var stack = [String]()
    var visited = [String]()
    var flag = Set<String>()
    flag.insert("ICN")
    stack.append("ICN")
    
    func dfs(){
        let cityname = stack.removeLast()
        visited.append(cityname)
        if let target = target[cityname]{
        for i in target{
            if !flag.contains(i){
                flag.insert(i)
                stack.append(i)
                dfs()   
            }
        }   
        }
    }
    
    dfs()
    
    print(visited)
    
    return ["dd"]
}

 

그래서 방문 배열도 딕셔너리 형태로 만들기로했다.

 

풀이

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    
    // 알파벳 순으로 앞선 결과를 원하기때문애 이렇게 정렬
    let sortedTickets = tickets.sorted{
        $0[1] < $1[1]
    }
    
    // DFS를 사용하면 된다. queue가 아닌 Stack
    // [:] String [String] 하면되지않을까. 
    var target = [String: [String]]()
    for ticket in sortedTickets {
        target[ticket[0],default:[]].append(ticket[1])
    }
    
    var used = [String: [Bool]]()
    
    for ticket in target.keys{
        used[ticket, default:[]] = [Bool](repeating: false, count: target[ticket]?.count ?? 0) 
    }
    
    var result = [String]()
    var stack = [String]()
    stack.append("ICN")
    
    func dfs(_ start : String) -> Bool {
        if result.count == tickets.count + 1 {
            return true
        }
        
        guard let arr = target[start] else { return false }

        for (index,destination) in arr.enumerated() {
            if used[start]?[index] == false {
                used[start]?[index] = true
                result.append(destination)
                if dfs(destination) {
                    return true
                }
                result.removeLast()
                used[start]?[index] = false
            }
        }
        
        return false
    }
    
    result.append("ICN")
    dfs("ICN")
    
    return result
}

 

어쨰서 DFS 방식을 사용해야하냐면 배열에 들어온 순서로 보았을때

ATL SFO ICN 이 있다면

처음에는 ATL 그 뒤에는 맨 뒤인 ICN이 stack 에 들어와야하기때문애 변형을 했다고 보면 된다.

 

 

일반적인 DFS

func normalDFS(_ start: String, _ visited: inout Set<String>) {
    visited.insert(start)
    
    if let nextNodes = graph[start] {
        for next in nextNodes {
            if !visited.contains(next) {
                dfs(next, &visited)
            }
        }
    }
}

 

위의 DFS

func dfs(_ start: String) -> Bool {
    if result.count == tickets.count + 1 {  // 1. 종료 조건이 다름
        return true
    }
    
    guard let arr = target[start] else { return false }
    for (index, destination) in arr.enumerated() {
        if used[start]?[index] == false {   // 2. 방문 체크 방식이 다름
            used[start]?[index] = true
            result.append(destination)
            if dfs(destination) {           // 3. 백트래킹 사용
                return true
            }
            result.removeLast()
            used[start]?[index] = false
        }
    }
    
    return false
}

 

1. 종료 조건
   • 일반 DFS: 모든 노드 방문
   • 현재 DFS: 모든 티켓 사용 (정확히 tickets.count + 1 개의 공항 방문)
2. 방문 체크
   • 일반 DFS: Set으로 노드 자체의 방문 여부 체크
   • 현재 DFS: 각 출발지별로 도착지의 사용 여부를 배열로 체크 (같은 경로를 여러 번 사용할 수 있음)
3. 백트래킹 사용
   • 일반 DFS: 단순 탐색
   • 현재 DFS: 경로가 불가능할 경우 되돌아가서 다른 경로 시도
4. 반환 값
   • 일반 DFS: void 반환
   • 현재 DFS: Bool 반환 (가능한 경로 찾았는지 여부)

이런 변형이 필요한 이유

1. 모든 티켓을 정확히 한 번씩 사용해야 함
2. 알파벳 순서가 앞서는 경로를 찾아야 함
3. 특정 경로가 불가능할 경우 다른 경로를 시도해야 함

 

이건 이전에 내가 작성한 정답 코드다

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    // 도착지를 기준으로 알파벳 순서로 정렬한다.
    let tickets = tickets.sorted { $0[1] < $1[1] }
    // 티켓의 사용여부를 기록
    var visited = [Bool](repeating: false, count: tickets.count)
    
    var result: [String] = []
    
    func dfs(start: String) {
        // 현재 방문한 도시 수가 티켓 수와 같다면 지금 도착한 곳이 마지막 여행지
        if result.count == tickets.count {
            result.append(start)
            return
        }
        for i in 0..<tickets.count {
            if tickets[i][0] == start && !visited[i] {
                visited[i] = true
                result.append(start)
                dfs(start: tickets[i][1])
                // 정답을 이미 구했다면 return
                if result.count == tickets.count + 1 {
                    return
                }
                result.removeLast()
                visited[i] = false
            }
        }
    }
    
    // 시작은 항상 "ICN"이라고 문제에서 주어짐
    dfs(start: "ICN")
    
    return result
}

 

지금 보니 이게 더 간단해보인다...;;