깊이/너비 우선 탐색(DFS/BFS) - 여행경로 (Lv.3) [2]

이문제 저번에도 풀었던 문제인데...이번에도 못풀었다.

너무 짜증난다... 일년이 지났는데 실력이 그대로라는 소리인거 같은 느낌

(사실...일한다고 열심히 한건 아니기에 크게 할말은 없지만... ㅠ.ㅠ 그래도 안한건 아니였다구,,,,)

 

쨌든 저번과 다른점이 있다면 이번에는 DFS로 접근했다는 사실이다.

그러나 재귀함수를 돌면서 결과값이 없어서 None이 나오는 문제를 반복(이 부분은 추후에 제대로 파헤쳐볼 것이다...)하다보니 해결 방법을 찾지 못하고, 결국 다른 사람의 풀이를 참고했다.

 

from collections import defaultdict

def dfs(ticketDict, N, start, result):
    
    if len(result) == N+1:
        return result

    for idx, end in enumerate(ticketDict[start]):
        ticketDict[start].pop(idx)

        copyResult = result[:]
        copyResult.append(end)

        ret = dfs(ticketDict, N, end, copyResult)

        ticketDict[start].insert(idx, end)

        if ret:
            return ret


def solution(tickets):
    answer = []
    
    ticketDict = defaultdict(list)
    N = len(tickets)

    for ticket in tickets:
        ticketDict[ticket[0]].append(ticket[1])
        ticketDict[ticket[0]].sort()

    answer = dfs(ticketDict, N, "ICN", ["ICN"])
    return answer

Sorted 함수는 새로운 리스트를 리턴하고, Sort()는 None을 리턴한다.