[프로그래머스] Lv3. 여행경로

3️⃣ 여행경로

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

💡 아이디어

ICN 공항에서 출발하여 공항 경로로 이동하는 것은 알겠는데, 문제는 가능한 경로가 2개 이상일 때 알파벳 순서가 앞서는 경로를 return하는 것을 어떻게 처리해줘야할지 전혀 감이안왔다.

예외를 고려하지 않고 BFS로 이렇게 생각했다.

그러나 각종 예외에 BFS로 어떻게 처리해야할지 난감해서 DFS로 방향을 틀었다

📝 풀이

생각을 바꿔보니 그냥 알파벳 순으로 미리 정렬하고 탐색하면 됐다.

DFS로 푸는게 너무 어려웠다..

from collections import deque
def solution(tickets):
    answer = []    
    for t in tickets:
        if t[0] == "ICN": #시작점이 인천이라면
            q = deque([t]) 
            while q:
                now = q.popleft() #큐에서 뺴기
                answer.append(now[0]) # 현재 출발지 넣어주기
                for nxt in tickets:
                    if now[1] == nxt[0]: #목적지와 출발지가 같은 것이 있다면
                        q.append(nxt) #다음 출발지를 q에 넣어준다
                        tickets.remove(now)
            
            # 맨 마지막꺼 넣어주기
            answer.append(tickets[0][1])
                        
    return answer