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

https://programmers.co.kr/learn/courses/30/lessons/43164?language=swift 

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

BFS/DFS

출발지와 도착지를 담은 비행기티켓들이 2차원 배열로 주어지면

모든 티켓을 한번씩 사용하는 여행 경로를 구하는 문제 (단 여러 경로가 있을시 알파벳이 더 빠른 경로가 우선)

 

접근방법

DFS로 풀지 BFS로 풀지 고민하다가 BFS로 풀었는데 다들 DFS로 풀었네..

이 문제는 BFS가 시간 복잡도가 더 큰 것 같다.

하지만 로직이 BFS가 조금 더 잘 와닿아서 이렇게 풀었다!

 

큐의 원소 : (cnt, current, adj, path)

- cnt : current 도시 까지 오는데 사용한 비행기 티켓 수

- current : 현재 도착한 도시

- adj : 비행기 티켓을 기반으로 만들어둔 인접리스트 딕셔너리 [출발지 : [도착지s]]

- path : current 까지의 경로

 

맨 처음 큐에 (무조건 ICN부터 출발하므로) (0, ICN, adj, [ICN]) 을 넣고 시작한다.

큐가 텅 빌 때까지 반복하는 while문에서

큐에서 pop하고, cnt가 모든 티켓의 수와 같은지 확인한다. 같으면 티켓을 다 썼다는 뜻이므로 path를 반환하고 종료

그렇지 않으면 current가 갈 수 있는 다음 도시로 이동해야한다.

다음 도시로 이동할 수 있을 때 큐에 push 하는 것 : (cnt+1, 다음도시, adj (이제 방문하는 티켓을 제거한), path+[다음도시] )

 

+ 추가로 인접리스트를 구하는 함수와 인접리스트의 도착지 배열을 정렬하는 함수를 따로 만들었다. 

 

오답노트

current 가 갈 수 있는 다음 도시로 이동할 때 for-in 문을 사용하는데

이때 adj에 current가 갈 수 있는 도시가 더이상 없는 경우 (배열이 비어있을 경우) 빈 배열을 넣어주고 반복문을 종료하게 해야한다. (이거때문에 core dumped 났었음)

 

+ 근데 테스트케이스 1번 시간이 너무 턱없이 많이 나온다.. dfs쓰는게 나을듯..

 

소스코드

import Foundation


func solution(_ tickets:[[String]]) -> [String] {
    
    var adj:[String:[String]] = makeAdjList(tickets)
    adj = getSortedAdj(adj)
    
    return getPath(tickets.count, adj)
}

func makeAdjList(_ tickets:[[String]]) -> [String:[String]] {
    var adj:[String:[String]] = [:]
    
    for ticket in tickets {
        if adj[ticket[0]] == nil {
            adj[ticket[0]] = [ticket[1]]
        } else {
            adj[ticket[0]]!.append(ticket[1])
        }
    }
    
    return adj
}

func getSortedAdj(_ adj:[String:[String]]) -> [String:[String]] {
    var _adj = adj
    for city in _adj {
        _adj[city.key] = city.value.sorted()
    }
    return _adj
}

func getPath(_ numOfTickets:Int, _ adj:[String:[String]]) -> [String] {
    var queue:[(cnt:Int, current:String, adj:[String:[String]], path:[String])] = []
    
    queue.append((0,"ICN",adj,["ICN"]))
    
    while (!queue.isEmpty) {
        let here = queue.removeFirst()
        if here.cnt == numOfTickets {
            return here.path
        }
        
        for (idx,next) in (here.adj[here.current] ?? []).enumerated() {
            var _adj = here.adj
            _adj[here.current]!.remove(at:idx)
            queue.append((here.cnt+1, next, _adj, here.path+[next]))
        }
    }
    
    return []
}