[Programmers] 여행경로

🔦 문제 링크

✍️ 풀이

---

• DFS 문제

조건에 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 하므로
티켓의 목적지를 기준으로 정렬을 수행한다. 이렇게 하면 빠른 알파벳부터 탐색을 하게 된다.

탐색을 하면서 사용한 티켓은 제거하고 목적지는 경로에 넣는다. dfs 빠져나오면 다시 티켓을 원래 위치에 넣어주고 경로에서도 빼준다. 이를 반복하며 첫번째로 모든 티켓을 소진해 발견한 경로가 답이된다.

🛠 코드

---

ret = []
def dfs(curr, tickets, answer):
    if not tickets:
        ret[:] = answer[:]
        return
    length = len(tickets)
    for i in range(length):
        if tickets[i][0] == curr:
            save = tickets[i]
            ticket = tickets[i][1]
            answer.append(tickets[i][1])
            tickets.pop(i)
            dfs(ticket, tickets, answer)
            tickets.insert(i, save)
            answer.pop()
        if ret:
            return ret
def solution(tickets):
    answer = []
    tickets.sort(key=lambda ticket:ticket[1])
    start = "ICN"
    answer.append(start)
    dfs(start, tickets, answer)
    return ret

✍️ 다른 사람 풀이(딕셔너리)

---

이차원 티켓 배열을 출발지를 key로 만들어 목적지들을 값으로 받아 변환했다.
이 또한 key값을 기준으로 정렬하면 알파벳 빠른 순부터 검사할 수 있다.

검사는 DFS를 통해 현재 위치를 기준으로 갈수 있는 목적지들을 모두 검사한다.
목적지가 선택되면 해당 목적지는 딕셔너리 값에서 삭제되고 경로에 추가된다.

이 선택이 가능하지 않다면 다시 딕셔너리 값의 원래 위치에 목적지를 삽입하고 경로에서는 삭제하도록 한다.

만약, 모든 티켓이 사용되었다면 그 때의 경로를 반환하도록 한다.

🛠 다른 사람 코드(딕셔너리)

from collections import defaultdict 

def dfs(graph, N, key, footprint):
    print(footprint)

    if len(footprint) == N + 1:
        return footprint

    for idx, country in enumerate(graph[key]):
        graph[key].pop(idx)

        tmp = footprint[:]
        tmp.append(country)

        ret = dfs(graph, N, country, tmp)

        graph[key].insert(idx, country)

        if ret:
            return ret


def solution(tickets):
    answer = []

    graph = defaultdict(list)

    N = len(tickets)
    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])
        graph[ticket[0]].sort()

    answer = dfs(graph, N, "ICN", ["ICN"])

    return answer

📝 정리

---

• DFS는 찾은 첫번째 값을 반환하기 위해서는 조건이 필요하다.

🎈 참조

---