[Swift] - 여행 경로

스위프트로 프로그래머스 "여행경로" 문제를 풀어보자

1. 문제 설명

"ICN" 에서 출발하여, 모든 비행기 티켓을 활용하여 갈 수 있는 경로 중 알파벳 순서가 가장 앞에 있는 경로를 출력하라

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

티켓 : [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]

정답 : ["ICN", "JFK", "HND", "IAD"]

티켓 : [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]

정답 : ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

2. 나의 풀이

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    var airports: [String] = []
    for flight in tickets {
        if airports.contains(flight[0]) == false {
            airports.append(flight[0])
        }
        if airports.contains(flight[1]) == false {
            airports.append(flight[1])
        }
    }
    for i in 0..<airports.count {
        for j in 0..<airports.count-1 {
            var idx1 = airports[j].startIndex
            var idx2 = airports[j+1].startIndex
            if airports[j][idx1] == airports[j+1][idx2] {
                idx1 = airports[j].index(after: idx1)
                idx2 = airports[j+1].index(after: idx2)
                if airports[j][idx1] == airports[j+1][idx2] {
                    idx1 = airports[j].index(after: idx1)
                    idx2 = airports[j+1].index(after: idx2)
                    if airports[j][idx1] > airports[j+1][idx2] {
                        airports.swapAt(j, j+1)
                    }
                } else if airports[j][idx1] > airports[j+1][idx2] {
                    airports.swapAt(j, j+1)
                }
            } else if airports[j][idx1] > airports[j+1][idx2] {
                airports.swapAt(j, j+1)
            } 
        }
    }
    var ans: [[String]] = [[]]
    var ret: [String] = ["ICN"]
    var icn: Int = airports.firstIndex(of: "ICN")!
    var cnt: [Int] = Array(repeating: 0, count: tickets.count)
    var tick = tickets
    func D(_ n: Int) -> [String] {
        if cnt == Array(repeating: 1, count: tickets.count) {
            ans.append(ret)
            return ret
        } else {
            for i in 0..<airports.count {
                if tick.contains([airports[n], airports[i]]) == true && cnt[tick.firstIndex(of: [airports[n], airports[i]])!] == 0 {
                    var idx = tick.firstIndex(of: [airports[n], airports[i]])!
                    tick[idx] = ["", ""]
                    cnt[idx] = 1
                    ret.append(airports[i])
                    D(i)
                    ret.removeLast()
                    tick[idx] = [airports[n], airports[i]]
                    cnt[idx] = 0
                }
            }
        }
        return []
    }
    D(icn)
    return ans[1]
}

3. 풀이 설명

일단, 알파벳 순서로 모든 공항들을 나열했다. 그래야 DFS 를 사용했을 때 , 가장 먼저 나오는 것이 알파벳순으로도 가장 앞에있는 경로가 되기 때문이다.

모든 티켓에 있는 출발지, 도착지를 airports[] 안에 넣은 후, 중복되면 거르고,

알파벳 순으로 sorting 을 해줬다, ( 버블정렬을 이용)

사실상 여기서 다 끝났다고 봐도 괜찮을 것 같다.
DFS를 잘 활용만 하면 끝이다.

이번에 cnt[] 는 티켓 수만큼 배열을 해준다.
티켓을 모두 사용하면, 즉 cnt가 [1, 1, 1, ...., 1] 이 되면 리턴을 해주는 방식이다.

여러 DFS문제들을 풀어보면서 나만의 패턴이 확립된 것 같다.

1. 탈출 조건

이번에 탈출 조건은 cnt가 [1, 1, 1, 1, 1, 1, ... ,1] 이 됬을 때 이다.
모든 티켓을 다 활용했기 때문에 빠져나와도 된다.

2. Lv이 올라갈 때 체킹

티켓을 사용했으면, 그 인덱스에 티켓을 ["", ""] 으로 바꿔버린다.
그리고 cnt[idx] = 1 로 바꿔준다.
ret.append(도착지) 해준다.

3. Lv이 내려갈 때 체킹

다시 티켓을 돌려준다. ["", ""] 을 [출발지, 도착지] 로 바꿔준다.
cnt[idx] = 0 으로 돌려주고
ret.removeLast() 로 지워준다.

결과는..

100점!