[프로그래머스/파이썬] 여행경로

내가 푼 풀이는 다음과 같은데 제출하니 4개 중 2개의 테스트케이스에서 시간 초과가 났다.

def solution(tickets):
    tickets.sort(key=lambda x:x[1])
    used = [0]*len(tickets)
    answer = ["ICN"]
    
    while tickets:
        a = answer[-1]
        for t in tickets:
            if a==t[0]:
                answer.append(t[1])
                tickets.remove(t)
                break
    return answer

하지만, 이 코드는

알파벳 순으로 정렬했을 때, 만약 ICN -> AAA 라는 경로, ICN-> BBB라는 경로가 있을 때, BBB->ICN이라는 경로만 있고, AAA에서 출발하는 티켓이 없을 때는 고려하지 않았다.

따라서 이를 고려해서 스택을 이용한 dfs 풀이에 대한 레퍼런스를 참고하여 풀었다.

 

참고 사이트

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