"여행경로"문제

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

---

내 코드

from collections import deque

#재귀 DFS 알고리즘, 인자로 (경로들어있는 리스트, 방문의 최대값, 시작점, 현재 거쳐온 경로)
def DFSTour(arr, max_len, start, PATH):
	
    #stack에 현재 경로값에 시작점을 더해준다.
    stack = PATH.copy()
    stack += [start]

	#더이상 경로가 없을때, 모든 도시를 방문했으면 stack리턴 아니라면 이전 도시에서 다른 경로를 탐색한다.
    if(not arr[start]):
        if(max_len+1 == len(stack)):
            return stack
        else:
            return

	# 시작점에서 갈수있는 목적지중, 알파벳순서로 뽑아 재귀로 들어가는데, 만약 결과값없이 돌아오면다면 (다른 경로가 있느데, 중간에 끝이라면) 뽑은 목적지를 다시 넣고 두번째 목적지를 꺼내서 재귀로 들어가본다.
    for i in range(len(arr[start])):
        result = []
        num = arr[start].popleft()   
        result = DFSTour(arr, max_len, num, stack)
        arr[start].append(num)

        if(result):
            return result

    return result

def solution(tickets):
    answer = []
	
    #알파벳 순서로 진행하기 위해 sort함
    tickets.sort(key = lambda x : x[1])
    #처음 시작점은 무조건 "ICN"부터 시작한다.
    dic = {'ICN' : 0}
    count = 1

    #편의를 위해 dic형과 list형으로 만든다.
    for ticket in tickets:
        for city in ticket:
            if(dic.get(city, -1) < 0):
                dic[city] = count
                count += 1
    cities = list(dic.keys())

    print(dic, cities)
    
    #경로를 deque로 저장할 것이다.
    arr = [deque() for i in range(len(cities))]
    
    #DFS를 위해 출발공항의 idx에 도착공항의 idx를 append해준다.
    for ticket in tickets:
        start = dic[ticket[0]]
        destination = dic[ticket[1]]

        arr[start].append(destination)

    answer = DFSTour(arr, len(tickets), 0, [])
    if(answer):
        for i in range(len(answer)):
            answer[i] = cities[answer[i]]
    return answer

---

개선

문제 분석

제한사항

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

• 모든 공항은 알파벳 대문자 3글자로 이루어 집니다.

• 주어진 공항 수는 3개 이상 10,000개 이하입니다.

• tickets의 각 행 [a,b]는 a 공항에서 b공항으로 가는 항공권이 있다는 의미입니다.

• 주어진 항공권은 모두 사용해야 합니다.

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

배경지식

🚩그래프

🚩스택과 큐

🚩깊이 우선 탐색 (DFS : Depth - First Search)

🚩너비 우선 탐색 (BFS : Breadth - First Search)

개선된 코드

• DFS 알고리즘의 응용한다. 또, 재귀 알고리즘을 사용한다.
• 방문하는 공항을 스택에 넣어가며 진행한다. 만약, 중간에 끊기는 공항이 있다면 다시 POP해서 다른공항으로 진행한다.

def solution(tickets):
    #dic형으로 경로를 저장할 것이다.
    dic = {}
    
    #dic에 시작점을 key로 목적지를 Value로 넣는다. O(N)
    for ticket in tickets:
        dic[ticket[0]] = dic.get(ticket[0], []) + [ticket[1]]
    
    #dic에서 pop해서 쓰기위해 sort(reverse=True)로 한다. O(N log N)
    for key in dic.keys():
        dic[key].sort(reverse=True)
    
    #시작점은 ICN
    stack = ["ICN"]
    
    #경로를 넣을 path
    path = []
    
    while stack: #O(N)
        #stack에서 시작점을 가져온다.
        top = stack[-1]
        
        #시작점에서 나가는 티켓이 아예 없거나 더이상 없을 때, path에 경로를 넣는다.
        if(not dic.get(top, 0) or len(dic[top]) == 0):
            path.append(stack.pop())
            
        #시작점에서 나가는 경로가 존재한다면 그것을 또다른 시작점으로 하고,
        #사용한 티켓은 제거한다.
        else:
            stack.append(dic[top][-1])
            dic[top].pop()
    
    return path[::-1]