[level 3] 여행경로

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

프로그래머스

핵심포인트

✅ collection으로부터 defaultdict를 import해줘서 딕셔너리 자료구조를 사용한다. 사용하는 함수는 init_graph()와 dfs() 두개!!

✅ init_graph():  2차원 배열으로 입력받는 ticket을 x[0],x[1]을 기준으로 sort한다음에 routes에 key(x[0])와 value(x[1])를 매핑시켜준다.

✅ dfs():  stack과 path(가려고 하는 경로를 저장하는 변수)를 세팅해준다음에 while len(stack)>0일때까지 if-else조건문에 따라 path 혹은 stack에 관련값을 append시켜준다. 

from collections import defaultdict

def solution(tickets):
    answer = []
    
    def init_graph():
        routes = defaultdict(list)
        
        tickets.sort(key = lambda x:(x[1], x[0]))
        
        for key, value in tickets:
            routes[key].append(value)
        return routes
    
    def dfs(start):
        stack = [start]
        path = [] # 가려고 하는 경로를 저장하는 변수
        while len(stack) > 0: # stack이 비어있을 때까지
            top = stack[-1] # 스택의 맨 뒤가 top
            print(stack)
            if top not in routes or len(routes[top]) == 0:
                path.append(stack.pop()) #여기서 바로 'return path'해주지 않는 이유가 
            	print("stack",stack)     #stack에 append한걸 차례대로 path에 append시켜주기위함
                print("path",path)
            else:
                stack.append(routes[top].pop(0))
        return path
            
    routes = init_graph()
    print(routes)
    answer = dfs("ICN")
    
    return answer[::-1]

 

[CHAT-GPT 답변]

• top은 현재 스택의 맨 위에 있는 도시를 나타냅니다.
• 만약 top에서 갈 수 있는 목적지가 없다면, top은 path에 추가되고 스택에서 제거됩니다. 이는 현재 경로의 끝에 도달했을 때의 상황입니다.
• 그러나 top에서 갈 수 있는 목적지가 있다면, 이러한 목적지 중 하나를 스택에 추가하고 routes에서 해당 목적지를 제거합니다. 이렇게 하면 다음으로 이동할 도시를 선택합니다. 이것은 현재 경로를 계속 확장하는 경우입니다.
• 요약하면, top이 path에 추가되는 것은 해당 경로가 끝났을 때이며, top의 목적지가 스택에 추가되는 것은 경로를 계속 확장할 때입니다.