[프로그래머스] 여행경로 (Python/파이썬)

<문제 링크>

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

프로그래머스

 

<풀이 전략>

1. 나는 별 생각없이 백트래킹으로 풀어서 통과했는데 다른 사람들 풀이 보니까 역순으로 dfs 한 번만에 푸는 풀이가 있어서 둘 다를 소개한다.

2. 백트래킹은 그냥 반환 조건을 잘 설정해서 백트래킹 함수를 구현하면 어렵지 않다.

3. DFS 풀이는 조금 특이한데 출발지가 'ICN'으로 고정되어있고 반드시 모든 도시를 여행할 수 있는 경로가 주어진다는 점을 이용해서 출발지를 고정하고 경로를 복원하는 방식이다.

4. 둘 다 통과는 가능하지만 DFS 풀이가 조금 더 발상이 필요한 대신 효율성 측면에서 유리하다.  

 

<정답 코드>

# 230122 여행경로(백트래킹)


def solution(tickets):

    # 변수 설정 및 초기화
    answer = []
    N = len(tickets)
    visited = [0 for _ in range(N)]


    # 백트래킹 함수 선언
    def backtracking(depth: int, current: str, route:list):
        nonlocal N, answer


        # 반환 조건
        if depth == N:
            if not answer or answer >= route:
                answer = route
            return

        # 백트래킹
        for i in range(N):

            if not visited[i] and tickets[i][0] == current:
                visited[i] = 1
                backtracking(depth + 1, tickets[i][1], route + [tickets[i][1]])
                visited[i] = 0

    backtracking(0, 'ICN', ['ICN'])


    return answer

 

# 230122 여행경로 (DFS)


from collections import defaultdict


def solution(tickets):
    
    answer = []
    ticket_dict = defaultdict(list)

    for ticket in tickets:
        ticket_dict[ticket[0]].append(ticket[1])
    
    
    for v in ticket_dict.values():
        v.sort(reverse=True)
    

    stack = ['ICN']

    while stack:

        top = stack[-1]

        if not ticket_dict[top]:
            answer.append(stack.pop())
        else:
            stack.append(ticket_dict[top].pop())

    answer.reverse()

    return answer