38. Reconstruct Itinerary

🎯 leetcode - 332. Reconstruct Itinerary

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 38번 문제

📌 날짜

2020.02.08

📌 시도 횟수

2 try / Failed

❌ (한번에 맞추지 못한 경우) 오답의 원인

😭 "여러 일정이 있는 경우 사전 어휘 순으로 방문한다"를 제대로 구현하지 못했다.
- input = [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]인 경우에 제대로 작동하지 않는다.
> 출력이 ['JFK', 'NRT', 'JFK', 'KUL'] 가 되어야 하는데
> 내것은 ['JFK', 'KUL']으로 잘못 출력된다. 

---

😉 다른 풀이

📌 하나. 재귀 DFS로 풀기

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        for start, last in sorted(tickets):
            graph[start].append(last)

        result = []

        def dfs(route):
            while graph[route]:
                dfs(graph[route].pop(0))
            result.append(route)
            print(result)

        dfs("JFK")
        return result[::-1]

💡 문제 해결 방법

*key point : 백트래킹 되면서 result에 담는다!
→ 가장 나중에 방문할 장소부터 result에 담고, 마지막에 [::-1] 연산으로 경로를 뒤집는다.

- 참고로 defaultdict 안쓰면 에러가 생길 것이다.
따라서 조건 따로 안 걸거면 defaultdict를 꼭 쓰는 걸 추천~~

• 글로 설명이 잘 안돼서 그림으로 이해했다.
  

😾재귀 DFS로 푸는 과정 눈으로 보기😾

---

📌 둘. 반복문으로 풀기

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        for start, last in sorted(tickets):
            graph[start].append(last)

        result, stack = [], ["JFK"]
        while stack:
            while graph[stack[-1]]:
                stack.append(graph[stack[-1]].pop(0))
            result.append(stack.pop())
        return result[::-1]

💡 문제 해결 방법

- 위의 재귀랑 원리는 같다.
- result는 위에랑 동일하게 경로를 "역순으로" 조회한 list이고
- stack은 그래프 조회 순서를 저장하기 위해 만든 스택이다.
만약 더이상 stack[-1] 뒤에 이어지는 추가적인 경로가 없다면 끝에서부터 차례대로 pop되면서 result에 담긴다.
----------------------------------------------------------------------------
⭐ 추가 설명 : stack이 왜 필요할까 ⭐
=> stack은 DFS에서 리프 노드까지 이동하는 과정을 차례대로 담은 것이다. 
=> DFS 재귀에서는 백트래킹 되면서 차례대로 담기지만, 
반복문에서는 추가적으로 경로를 담고 있는 스택을 생성해서 사용해야 한다.
=> 더 이상 stack[-1]의 요소에 대해 이어지는 경로가 없으면 pop()되어 result에 저장한다.
=> 다만 pop()하다가 만약 중간에 경로가 남아있는 요소가 있다면 다시 리프노드까지 
이동하는 과정을 차례대로 stack에 담는다.
----------------------------------------------------------------------------
- 막히는 부분(더이상 경로 없는 경우)일 경우 while문을 돌지 않고 바로 result.append()로 넘어간다.
- 따라서 더이상 경로가 없기 때문에 stack에 담기지 않고 바로 result에 삽입된다.

• 직접 그림으로 그려가며 이해했다.
  

😾반복문으로 푸는 과정 눈으로 보기😾