[프로그래머스-DFS/BFS] 여행경로_파이썬 ❌❌

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

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

---

from collections import defaultdict


def solution(tickets):
    tickets.sort(reverse = True)
    
    dic = defaultdict(list)
    for t1, t2 in tickets:
        dic[t1].append(t2)
        
    answer = []
    stack = ["ICN"]
    while stack:
        now = stack[-1]
        if not now in dic or len(dic[now]) == 0:
            answer.append(stack.pop())
        else:
            stack.append(dic[now].pop())
    
    answer.reverse()
    return answer

경로가 2개 이상일 때 알파벳 경로가 앞서는 경우를 선택해야한다. 그렇기 때문에 정렬을 수행한다.

여기서는 내림차순 정렬을 수행했는데, 나중에 있을 pop을 위해서다. 풀이대로 연산을 진행하면 결과 순서가 거꾸로 된다. 따라서 마지막에 reverse 함수를 이용해 순서를 원래대로 돌려 놓는다.

---

from collections import defaultdict


def dfs(dic, l, key, routes):
    if len(routes) == l+1:
        return routes
    
    for i, city in enumerate(dic[key]):
        temp = routes[:]
        temp.append(dic[key].pop(i))
        
        result = dfs(dic, l, city, temp)
        
        dic[key].insert(i, city)
        
        if result:
            return result

def solution(tickets):
    l = len(tickets)
    
    dic = defaultdict(list)
    for t1, t2 in tickets:
        dic[t1].append(t2)
        dic[t1].sort()
    
    answer = dfs(dic, l, 'ICN', ['ICN'])    
    return answer

이 풀이에선 오름차순 정렬을 수행하고 dfs를 돌린다. 

처음은 알파벳 순서대로 경로를 설정하지만, 만약 해당 경로로 모든 도시를 방문하지 못한다면, for문에서 pop했던 요소를 insert를 이용해 다시 제자리에 넣고 다른 경로를 선택해야한다.

 

예를들어 tickets = [['INC', 'ABC'], ['INC', 'BBC'], ['BBC', 'DEF'], ['DEF', 'INC']]

알파벳 순서대로라면 'INC'에서 'ABC'가 첫 경로로 선택되야 하지만, 그 경우의 수는 불가능 하기 때문에 'INC'에서 'BBC'의 경로를 선택해야한다.