🥚문제

https://programmers.co.kr/learn/courses/30/lessons/43164

• DFS/BFS

---

🥚입력/출력

---

🍳코드

import copy
from collections import defaultdict

routes = []


def solution(tickets):
    # dictionary
    info = defaultdict(list)
    for ticket in tickets:
        a, b = ticket
        info[a].append(b)

    dfs(tickets, info, "ICN", 0, "ICN")
    routes.sort()
    answer = routes[0].split()
    return answer


def dfs(tickets, info, start, cnt, route):
    if cnt == len(tickets):
        routes.append(route)
        return

    if start in info:
        for end in info[start]:
            new_info = copy.deepcopy(info)
            new_info[start].remove(end)
            dfs(tickets, new_info, end, cnt + 1, route + " " + end)

---

🧂아이디어

DFS

• tickets에 담긴 출발지, 목적지 정보를 dictionary 형태로 가공한다.
  {출발지1:[목적지1, 목적지2], 출발지2:[목적지3], ...}

• dfs를 통해 경로를 구한다.

• start 공항에서 갈 수 있는 end공항이 있다면, info[start]에서 end공항을 제외한(항공권 사용) new_info를 생성하고
  dfs(tickets, new_info, end, cnt + 1, route + " " + end)를 해준다.

• cnt가 ticket의 길이와 같아지면 주어진 항공권을 모두 사용한 것이다.
  지금까지의 공항 경로인 route를 모든 공항 경로를 저장하는 전역변수 routes에 삽입한다.

• dfs를 마친 뒤, routes에는 주어진 항공권으로 갈 수 있는 모든 경로가 저장되어 있다.
  만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return해야한다.
  따라서 routes.sort()를 통해 정렬해주고, 정답 형식에 맞게 가장 앞에 있는 문자열을 공백 기준으로 나눈 리스트를 반환한다.