[프로그래머스] DFS/BFS - 여행 경로

🎯 programmers : 깊이/너비 우선 탐색 - 여행 경로

---

🤔 나의 풀이

📌 문제

- 프로그래머스 코딩테스트 연습 > 깊이/너비 우선 탐색 > Level 3 여행 경로

📌 날짜

2021.03.09

📌 시도 횟수

5 try

💡 DFS로 풀기

from collections import defaultdict


def solution(tickets):
    tdict = defaultdict(list)
    for start, end in sorted(tickets): # 알파벳 순으로 방문하므로 sorted를 해줌!
        tdict[start].append(end)
    answer = []

    def dfs(node):
        if not tdict[node]:
            return node

        while tdict[node]:
            next = tdict[node].pop(0)
            answer.append(dfs(next))
        return node

    dfs("ICN")
    answer.append("ICN")
    return answer[::-1]

💡 문제 해결 방법

• 
• [["ICN", "A"], ["ICN", "B"], ["B", "ICN"]]인 여행 경로가 있다고 가정하자.
• 이 경로의 탐색 순서는 ICN > B > ICN > A가 되어야 한다.

🌼더이상 경로가 없으면 담는다🌼 를 기억하자!
- 즉, answer에 먼저 저장되는 경로는 더 나중에 방문한 경로임을 이해하자.

🌼 코드 설명
1. 먼저 주어진 경로 list로 key는 출발지, value는 도착지인 dict를 만든다.
2. 방문한 경로에 대해서는 value를 pop함으로써 제거한다.
3. 그러나, 만약 더 이상 현재 node에서 갈 수 있는 경로가 없는 경우
(pop할 수 있는 value가 없는 경우), 현재 node를 리턴한다.
4. 먼저 리턴되는 순서로 경로를 answer에 저장한다. 
즉, dfs를 돌면서 answer에 저장되는 경로들의 순서는 구하고자 하는 경로를 뒤집은 결과이다. 
(나중에 방문하는 경로부터 차례대로 저장된다)
5. dfs가 완료되면 최종적으로 시작점인 "ICN"를 맨 마지막에 담고 answer[::-1]를 리턴한다.

💡 새롭게 알게 된 점

- 

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

- 내가 잘못 생각한 부분이 있었다.
- [["ICN", "A"], ["ICN", "B"], ["B", "ICN"]]인 여행 경로가 있다고 가정했을때,
나의 예전 풀이는 "무조건 2개의 경로가 있으면 알파벳 순부터 방문한다"라는 생각에 의해
위의 여행 경로에서 ICN 다음으로 (A와 B) 중 무조건 A를 먼저 answer에 담는 풀이었다.
- 그러나 이 풀이의 경우, [ICN > A]까지만 이동하고 A 다음에 더이상 경로가 없어 프로그램이 종료된다.

- 따라서 '먼저 방문하는 경로'부터 answer에 저장하는 대신, 
'나중에 방문하는 경로'. 즉 먼저 리턴되는 경로들부터 answer에 담은 뒤에,
최종적으로 answer를 뒤집어 줌으로써 내가 구하고자 하는 경로를 구할 수 있었다.