여행경로

DFS ( recursive ) 안에서 loop로 return 할 때,
None 을 리턴하는 문제가 나이게서 발생하는데,
https://stackoverflow.com/questions/63042421/python-recursive-function-doesnt-execute-rest-of-the-outer-loop-when-returned

보통 recursive 안의 loop 안에서 return 하면 자주 발생하는 문제인 것 같다..

import numpy as np
import copy

def dfs(node, graph, visited, route, tickets):

        remain_node = copy.deepcopy(node)
        remain_visited = copy.deepcopy(visited)
        remain_route = copy.deepcopy(route)
        
        for possible_end in graph[node]:
            node = copy.deepcopy(remain_node)
            visited = copy.deepcopy(remain_visited)
            route = copy.deepcopy(remain_route)

            print('current_node :', node)
            print('possible_end :', possible_end)
            print('route : ', route)
            print(visited)
            if visited[node+possible_end] == True:
                pass
            # 티켓을 사용했으면 티켓 제거
                # 반례 : 중복 티켓 존재 가능성이 있음
                # 
            # 티켓 개수 + 1 이하라면 방문
            elif visited[node+possible_end] == False and len(route)<=len(tickets)+1: # visited : 티켓 사용 여부
                visited[node+possible_end] = True
                route.append(possible_end)
                
                if len(route)==len(tickets)+1:
                    print(len(route))
                    print(len(tickets)+1)
                    print('route ! : ', route)
            
                    return route
                dfs(possible_end, graph, visited, route, tickets)
                


def solution(tickets):
    # tickets=[["ICN", "B"], ["B", "ICN"], ["ICN", "A"], ["A", "D"], ["D", "A"]]
    # ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]
    # ['ICN', 'COO', 'DOO', 'COO', 'BOO', 'ICN', 'BOO', 'DOO', 'BOO']
    # [["ICN", "AAA"], ["ICN", "AAA"], ["ICN", "AAA"], ["AAA", "ICN"], ["AAA", "ICN"]]
    # [["ICN", "B"], ["B", "ICN"], ["ICN", "A"], ["A", "D"], ["D", "A"]]
    
    nodes = []
    for s,e in tickets:
        nodes.append(s)
        nodes.append(e)
        
    nodes = np.unique(nodes)
    graph = {}
    
    for node in nodes:
        _ = []
        for s,e in tickets:
            if node == s:
                _.append(e)
        _.sort()
        graph[node] = _

    visited = {}
    for s,e in tickets:
        visited[s+e] = False
        
    print('nodes :', nodes)
    print('graph :',graph) # 
    print('visited :',visited)
    
    route = ['ICN']

    answer = dfs('ICN', graph, visited, route, tickets)
    print(answer)
    return answer
    ```