Leetcode 78

언어: python3

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        for src,dest in tickets:
            if graph[src]:  # if not empty
                graph[src].append(dest)
            else:
                graph[src] = [dest]
        current = "JFK"
        itinerary = []
        
        def dfs(current:str,path:List[str]):
            if len(tickets) ==0 : # ending condition
                itinerary.append(path[:])
                return
            dests = graph[current]   # dests is an array containing possible destinations
            
            if len(dests)==1:
                if [current,dests[0]] not in tickets:
                    return
                path.append(dests[0])
                tickets.remove([current,dests[0]])
                
                dfs(dests[0],path[:])
                tickets.append([current,dests[0]])
                return
            
            for dest in dests:
                if [current,dest] not in tickets:
                    continue
                else:
                    path.append(dest)
                    tickets.remove([current,dest])
                    dfs(dest,path[:])
                    tickets.append([current,dest])
                    path.pop()
                
        dfs("JFK",["JFK"])
        itinerary = sorted(itinerary)
        print(itinerary)
        return itinerary[0]
            

• 위의 방법으로 한 결과 timeout 발생

• 모든 itinerary 구한 후 다시 sorting 한 원인이라고 생각됨

  working solution

  class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        for src,dest in sorted(tickets,reverse=True): # we want sorted order
            if graph[src]:  # if not empty
                graph[src].append(dest)
            else:
                graph[src] = [dest]
        current = "JFK"
        itinerary = []
        
        def dfs(current):
            while graph[current]:
                dfs(graph[current].pop())
            itinerary.append(current) # this will be added in reverse order
        
        dfs(current)
        return itinerary[::-1] # return result in reversed order

• 아직 확실히 이해 못해서 다시 봐야 함

• 위의 조건만으로 모든 경우를 탐색할 수 있는 이유?