[Python] 여행 경로

def solution(tickets):
    
    path = {}
    
    for (start, end) in tickets:
        path[start] = path.get(start, []) + [end]
    
    for r in path.keys():
        path[r].sort(reverse=True)
  
    answer = []       
    stack = ["ICN"]  
    while stack :
        now = stack[-1]
        if now not in path or len(path[now]) == 0 :
            answer.append(stack.pop())
        else :
            stack.append(path[now][-1])
            path[now] = path[now][:-1]

    return answer[::-1]

---

풀이

1. 딕셔너리로 변환한 tickets를 while문을 돌면서 'ICN'부터 시작해 이어진 경로를 스택으로 쌓아준다. (쌓은 경로는 딕셔너리에서 제거)

2. 경로가 더이상 없을 경우 해당 도시를 answer에 추가해준다.

3. stack에 쌓았던 다음 도시를 pop을 통해 꺼내오고, 연결되어있는 도시가 있는지 확인한다. (있다면 1번으로, 없다면 2번으로)

4. 이를 stack이 빌때까지 반복하고,  answer에는 경로가 반대로 저장되게 되므로 answer[::-1]를 반환해준다.

 

1) 2차원 배열 리스트 tickets을 딕셔너리로 만들기

    path = {}
    
    for (start, end) in tickets:
        path[start] = path.get(start, []) + [end]

    for r in path.keys():
        path[r].sort(reverse=True)

 

1. 2차원 배열 리스트 tickets을 딕셔너리로 만든다. 

• 예) path = {'ICN':[ "ATL", "SFO"]}
• get(x) 함수 : x라는 Key에 대응하는 Value를 되돌려준다. path.get(start)는 path[start]와 같다. 하지만 딕셔너리안에 찾으려는 Key 값이 없을 경우, 미리 정해 둔 디폴트 값을 대신 가져오게 하고 싶을 때에는 get(x, '디폴트 값')을 사용하면 편리하다.

 

2. 나중 while문을 돌면서 stack에 경로를 저장하고 pop을 통해 끝에서부터 answer에 저장하는 방식이므로, 딕셔너리 value들을 역순으로 해준다.

• 예) path = {'ICN':[ "SFO", "ATL"]}
• 예) tickets = [["ICN", "B"], ["B", "ICN"], ["ICN", "A"], ["A", "D"], ["D", "A"]] 경우, 
  • path = {'ICN': ['B', 'A'], 'B': ['ICN'], 'A': ['D'], 'D': ['A']} 
  • while else을 돌아 stack = ['ICN', 'A', 'D', 'A'] 까지 저장했을때, 
  • path = {'ICN': ['B'], 'B': ['ICN'], 'A': [], 'D': []} 라서 'A'가 if문으로 가게 된다.
  • 따라서 pop을 통해 끝의 'A'부터 answer에 저장되어진다. (answer = ['A', 'D', 'A'] )
  • 최종 answer  = [ 'A', 'D', 'A', 'ICN', 'B', 'ICN'] (나중에 return에서 뒤집어준다.)

 

2) DFS

    answer = []       
        
    stack = ["ICN"]  
    while queue :
        now = stack[-1]
        if now not in path or len(path[now]) == 0 :
            answer.append(stack.pop())
        else :
            stack.append(path[now][-1])
            path[now] = path[now][:-1]
                       
    return answer[::-1]

1. stack에서 가장 최근에 저장된 도시를 꺼내온다.

2. 만약 해당 도시가 path 딕셔너리에 없거나, 해당 도시로 시작점으로 하는 티켓이 없을 경우, 

    stack에서 꺼내와 answer에 추가한다.

3. 2번이 아니라면, path에서 꺼내와 stack에 저장하고, 해당 도시는 value 값에서 지워준다.

4. while문이 끝나면 answer을 역순으로 반환한다.

 

 

 

 

 

---

참조

https://gurumee92.tistory.com/165