[Programmers/Swift] 여행경로

Programmers

코딩테스트 연습 - 깊이/너비 우선탐색(DFS/BFS) - 여행경로 (Lv. 3)

코딩테스트 연습 - 여행경로

---

TODO :

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다.

항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때,

방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

Constraints : 

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

 

Sample Input :

tickets
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]

 

Sample Output :

return
["ICN", "JFK", "HND", "IAD"]
["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

 

Solution.swift : 

//  Created by Yongwoo Marco on 2021/08/07.
//  Copyright © 2020 Yongwoo Marco Kim. All rights reserved.
//
import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    var paths = [[String]]()

    fly("ICN", passed: [], left: tickets, visited: &paths)
    
    return paths.first!
}

func fly(_ to: String, passed: [String], left: [[String]], visited: inout [[String]]) {
    if left.isEmpty { visited.append(passed + [to]) }

    let tickets = left.filter({ $0[0] == to }).sorted(by: { $0[1] < $1[1] })
    
    for ticket in tickets {
        var removed = left
        removed.remove(at: removed.firstIndex(of: ticket)!)
        fly(ticket[1], passed: passed + [to], left: removed, visited: &visited)
    }
}

github Code Repositoriy

 

How I tried this :

"항상 "ICN" 공항에서 출발합니다. 조건과

• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

라는 조건 때문에 티켓을 줄여가면서 풀면 되겠다고 생각했다. 남은 티켓은 반드시 없을 예정이기 때문에...

 

fly() 함수는 다음으로 갈도시를 지정해주면

그 도시로 갈 수 있는 티켓을 골라주고  tickets + (각 티켓의 도착지를 알파벳 정렬시킴)

각 티켓 수 만큼 지난 도시들(passed), 남은 티켓(left)를 품고 fly() 한다.  

 

남은 티켓이 없는 상황(모든 여행이 끝난 상황)은 여태 지난 도시들 순서(passed)를 paths에 쌓아준다.

 

만약 다음 행선지가 없는 경우는 tickets가 빈 배열이고 for문을 돌지 않으니 그대로 fly 함수가 종료된다

(paths에 배열 업데이트 없음)

다양한 경우의 수를 나름 생각해보았지만 계속 결과는 같았다.

테스트케이스대로 답은 잘나오는데 어디서 문제인지 원인을 찾을 수 없었다.

 

1시간이상 시간을 소요한거 같아서 결국 질문하기를 보았는데

"1번 테스트만 실패하거나 런타임 에러 뜨시는 분! 저는 이렇게 해결했습니다!"  라는 글이 있어서 보니

이 분이 언급한 문제는 동일한 티켓이 여러개 있는점이었다.

 

딱 보자마자 알아 버렸다... 그런 가능성은 생각해본적이 없었다.

다시보니 내 코드에서는 같은 티켓은 싹 걸러서 버리는 부분이 있었다.

// 이전 코드
for ticket in tickets {
    fly(ticket[1], passed: passed + [to], left: left.filter({ $0 != ticket }), visited: &visited)
}
    
// 정답 코드
for ticket in tickets {
    var removed = left
    removed.remove(at: removed.firstIndex(of: ticket)!)
    fly(ticket[1], passed: passed + [to], left: removed, visited: &visited)
 }

filter로 현재 티켓이 아닌 걸 모두 걸러내면 동일한 티켓이 있는경우 1개 티켓이 아니라 여러개가 걸러지고

 

"모든 도시를 방문할 수 없는 경우는 주어지지 않습니다." 조건을 충족시키는 테스트케이스가 붕괴되서

결국 런타임 에러나 실패가 일어난 것이었다..

 

딱 해당 티켓 1개만 제거한 left를 넘겨주는 코드로 변경하니

참 파란색 이쁘다....

 

시간복잡도 생각해보기

... 졸려 다음에..

 

What I got is : 

문제의 설계는 잘한 것 같지만 힌트가 없었다면 이유를 몰랐을 문제라서 결국은 해결하지 못한거나 다름없다..

하지만 긍정적인 면도 있다. 먼가 내가 swift 스럽게 코드를 잘 짰다고 할까...

사실 질문하기 들어가보기전에 "swift 여행경로" 키워드로 찾아본 블로그들은

힌트를 얻기엔 내 코드 스타일과 너무 달랐다.. C++ 할때 내 모습이었지만

 

I have to study :

 

문제에 관한 모든 저작권 : https://programmers.co.kr/

프로그래머스