[Python] 프로그래머스 LV.03 - 여행경로 (+) test case

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

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

[ 알고리즘 ]

DFS

 

[문제 접근]

아 이 문제 때문에 애를 많이 먹었다.. 사전 순으로 정렬을 시켜야하나, 또 그것이 타고타고 갔을 때 끊겨버리면 안되기 때문에, 하나의 공항에서 끝까지 갔을 때 이어지는지 여부를 따로 체크하려고하다보니 많이 복잡해졌다..

 

DFS를 이용하여 항공편이 더이상 남아있지 않았을 경우에만 pop하여 answer에 저장해주고,

남아있을 경우엔 계속 스택에 넣어주는 방법으로 해결

 

질문하기 탭에서 이것 저것 테케를 구했는데 그 중에서 문제 해결에 도움된 것 들

 

Parameters

[["ICN", "B"], ["B", "ICN"], ["ICN", "A"], ["A", "D"], ["D", "A"]]

Return

["ICN", "B", "ICN", "A", "D", "A"]

 

Parameters

[["ICN", "A"], ["ICN", "A"], ["A", "ICN"], ["A", "C"]]

Return

["ICN", "A", "ICN", "A", "C"]

 

Parameters

[["ICN", "A"], ["ICN", "B"], ["B", "ICN"]]

Return

["ICN", "B", "ICN", "A"]

 

Parameters

[["ICN", "A"], ["ICN", "A"], ["ICN", "A"], ["A", "ICN"], ["A", "ICN"]]

Return

["ICN", "A", "ICN", "A", "ICN", "A"]

 

Parameters

[["ICN", "A"], ["A", "C"], ["A", "D"], ["D", "B"], ["B", "A"]]

Return

["ICN", "A", "D", "B", "A", "C"]

 

 

 

[코드]

from collections import defaultdict
from collections import deque
def solution(tickets):
    result = []
    answer=[]
    stack=deque()
    dic=defaultdict(list)
    
    #정렬
    tickets=sorted(tickets,key=lambda x:x[1])
    
    for i in tickets:
        a=i[0]
        b=i[1]
        dic[a].append(b)
            
    stack.append('ICN')
    
    while stack:
        ptr=stack[-1]
        
        if len(dic[ptr])!=0:
            stack.append(dic[ptr].pop(0))
        else:
            result.append(stack.pop())
    
    # 역순
    for i in range(len(result)-1,-1,-1):
        answer.append(result[i])
                        
    return answer