Reconstruct Itinerary - LeetCode

문제 접근 🤔

• 사전순으로 방문해야하므로, 리스트를 value로 하는 딕셔너리 형태로 그래프를 구성하되 각각의 key가 정렬된 value를 가지도록 하면 되겠다.
• 이후, 해당 그래프에서 JFK에서 시작하여 하나씩 value를 꺼내면 정답을 구할 수 있을 것이다.
  
  
  

놓쳤던 부분 😅

• 조금 어렵게 접근해서 테스트 케이스는 맞는데 제출하면 틀린 풀이를 냈다가 답안을 보니 생각보다 꽤나 쉬웠던 로직.
• 아직 DFS와 BFS가 안 익숙해진 것 같다.
  
  
  

코드 😁

파이썬 코드(85 ms)

from collections import defaultdict
class Solution:
    def findItinerary(self, tickets):
        graph = defaultdict(list)
        route = []

        for departure, arrival in sorted(tickets):
            graph[departure].append(arrival)

        def dfs(start = "JFK"):
            while graph[start]:
                dfs(graph[start].pop(0))
            route.append(start)
        dfs()
        return route[::-1]

자바스크립트 코드(74 ms)

const findItinerary = (tickets) => {
  const graph = new Map();
  route = [];

  tickets.sort().forEach(([departure, arrival]) => {
    if (!graph[departure]) {
      graph[departure] = [];
    }
    graph[departure].push(arrival);
  });

  const dfs = (start = 'JFK') => {
    while (start in graph && !!graph[start].length) {
      dfs(graph[start].shift());
    }
    route.push(start);
  };
  dfs();
  return route.reverse();
};