BFS/DFS - 여행 경로

이번 문제는, 재귀적인 탐색을 통해서 조건에 맞는 경로를 탐색하는 문제입니다.

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

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

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

 

문제를보면, N개의 여행 티켓이 주어지고

 

ICN을 출발해서 모든 도시를 최소 한번씩은 방문하고, 모든 티켓을 사용해야됩니다.

 

모든 디켓을 사용하기 때문에, 모든 티켓을 사용하는 완전탐색을 진행하고,

 

조건에 맞는 Case를 모두 뽑는다면 원하는 정확한 답은 얻을 수 있습니다.

 

하지만, 공항의 수가 3 이상 10000개 이하이기 때문에,

 

O(n!)이 걸리는 완전탐색으로는 사실상 정답은 찾기 어렵습니다.

 

--BFS/DFS 이용하기

문제에서 처음 시작을 ICN으로 고정하였기 때문에, ICN을 시작으로 하는 Ticket의 개수만큼 DFS를 진행해줍니다.

 

아래는 테스트케이스 2번([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]])

 

의 경우 2개의 ICN 출발 Ticket을 사용해서 두개의 DFS탐색을 진행하는 예제 추상화 이미지입니다.

다수의 DFS 탐색 추상화 이미지

ICN으로 시작하는 Ticket을 시작으로, 이후 목적지에서 출발하는 Ticket를 재귀적으로 탐색한 후

 

최종적으로 모든 Ticket을 사용했는지와 모든 도시를 방문했는지 검증하여 후보를 추립니다

 

마지막으로, 모든 경우의 수 중 알파뱃이 가장 빠른순 한가지 Case를 제출하면 정답이 됩니다.

 

아래는 Python으로 구현한 정답입니다 :)

 

#순환호출 내에서 구한 Case를 저장할 List를 선언
answer = []    

def dfs(loc_list, remain_list, starting):    
    #이전 Ticket으로 도착한 지점에서 출발이 가능한 Ticket을 찾습니다.
    for i in range(len(remain_list)):
        if remain_list[i][0] == starting[-1]:
            #방문한 도시의 Array(Set)을 최신화 해주고
            #남은 Ticket을 통해서 탐색을 계속합니다.
            dfs(loc_list-set(starting), remain_list[:i]+remain_list[i+1:], starting + [remain_list[i][1]])    
    #모든 Ticket을 사용하고 모든 도시를 들렀다면, 정답중 하나이므로 저장
    if len(loc_list-set(starting))==0 and len(remain_list)==0:        
        answer.append(starting)

def solution(tickets):    
    #Ticket으로 방문할 수 있는 모든 도시의 List를 구합니다.
    temp= []    
    for i in tickets:
        temp += i    
    #최초 Ticket List중 ICN을 시작하는 Ticket을 찾고, DFS를 시작합니다.
    for i in range(len(tickets)):
        if tickets[i][0]=="ICN":
            dfs(set(temp), tickets[:i]+tickets[i+1:], tickets[i])
    #마지막으로 알파뱃 기준으로 가장 빠른 Case를 반환
    return sorted(answer)[0]