[프로그래머스] Python 여행경로 Level3 - DFS/BFS

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

접근

1. 정렬을 신경쓰다 보면 다음과 같은 케이스를 통과하지 못한다.
   [["ICN", "BBB"], ["ICN", "CCC"], ["CCC", "ICN"]]
   • "BBB"가 "CCC"보다 앞서기 때문에
     "ICN", "BBB"를 먼저 가게되면 더 이상 갈 수 있는 곳이 없다.
   • 때문에 완전 탐색을 해야 한다. "ICN", "BBB"를 갔다가 갈 곳이 없으면 "ICN", "CCC"를 가는 방법으로.
2. 다음과 같은 알고리즘이 필요하다.
   • 출발을 기준으로 도착을 덧붙이는 딕셔너리 형태로 리스트를 구성한다. ex)
     ICN : BBB, CCC
     CCC : ICN
   • 이때 도착을 기준으로 정렬한다.
     ICN : CCC, BBB
     CCC: ICN
   • 초기값인 ICN을 스택에 넣고 ICN의 키 중 뒤에 값을 빼내며 순회를 한다.
   • 이때 키값이 돌아갈 곳이 없다면 임시 리스트에 저장을 해준다.

stack = ["ICN"] // 시작값 스택에 저장
path = []
temp = ""

stack = ["ICN", "BBB"] // 2. 출발, 도착 저장
path = []
temp = "ICN" // 1. 스택 값 pop

stack = ["ICN"] 
path = ["BBB"] // 2. 출발할 곳 없어 저장
temp = "BBB" // 1. 스택 값 pop

stack = ["ICN", "CCC"] // 2. 출발, 도착 저장
path = ["BBB"]
temp = "ICN" // 1. 스택 값 pop

stack = ["ICN", "CCC", "ICN"] // 2. 출발, 도착 저장
path = ["BBB"]
temp = "CCC" // 1. 스택 값 pop

stack = ["ICN", "CCC"] 
path = ["BBB", "ICN"] // 2. 갈 곳 없어 저장
temp = "ICN" // 1. 스택 값 pop

stack = ["ICN"] 
path = ["BBB", "ICN", "CCC"]
temp = "ICN" 

stack = []
path = ["BBB", "ICN", "CCC", "ICN"]
temp = "ICN"

path 역순 출력
"ICN", "CCC", "ICN", "BBB"

슈도코드

dict 출발: [도착] push
도착을 기준으로 sort

stack 초기 값 push

while stack
  stack값 pop
  
  만약 갈 공항이 없다면 
    끝이라는 뜻이니 path에 저장
  아니면 갈 곳이 있다는 뜻이니
    stack에 다시 출발과 
    도착을 저장. 이 때 도착은 dict빼줘야됨. 간 곳이니까
    
 역순으로 출력

풀이

from collections import defaultdict

def solution(tickets):
    graph = defaultdict(list)
    
    for start, end in tickets:
        graph[start].append(end)
        
    for end in graph.keys():
        graph[end].sort(reverse=True)
        
    stack = ["ICN"]
    path = []
    
    while stack:
        temp = stack.pop();
        
        if temp not in graph or not graph[temp]:
            path.append(temp)
        else:
            stack.append(temp)
            stack.append(graph[temp].pop())
    
    return path[::-1]