[Programmers] Level 3. 여행경로

🔗 Problem Link

프로그래머스

---

❔Thinking

• 출발지, 도착지가 적힌 ticket이 주어질 때, 모든 여행지를 방문하는 여행 경로를 반환한다. 

---

💻Solution

from collections import defaultdict
def solution(tickets):
    answer = []
    # ticket 도착지 내림차순 정렬
    tickets = sorted(tickets, key=lambda x: x[1], reverse=True)
    # 티켓 그래프 생성
    tickets_dict = defaultdict(list)
    for t in tickets:
        tickets_dict[t[0]].append(t[1])
    # dfs
    stack = ['ICN']
    while stack:
        start = stack.pop()
        if not tickets_dict[start]:
            answer.append(start)
        else:
            stack.append(start)
            stack.append(tickets_dict[start].pop())
    return answer[::-1]

---

🗝️keypoint

1. 주어진 값을 연속해서 찾아가는 문제의 경우, dfs를 활용하면 효과적이다.
2. 주어진 값의 인접행렬이나 그래프 형태로 바꾸어야 dfs를 활용할 수 있다.