[프로그래머스] 여행경로 -python 파이썬

문제

 

 

이전의 도착지를 다시 출발지로 설정하여 재귀를 통해 문제를 해결해줄 수 있으므로 bfs보다는 dfs를 통해서 문제를 해결해주는게 적절한 문제이다.

 

이때 알파벳의 순서가 앞서는 경로를 우선시 해주므로 재귀함수를 실행하기전에 sort() 내장함수를 통해 정렬을 해주고

가능한 경로가 2개이상인 경우도 있기때문에 이에대한 처리 또한 해주어야 한다.

 

 

나의  코드

def solution(tickets):
    answer = []
    #알파벳 순서가 앞서는 경로 먼저 방문하기 위해 처리
    tickets.sort(key = lambda x:(x[0],x[1]))
    visited = [False] * len(tickets)
    
    def dfs(pre, path):
        #마지막에 하나 더 추가되는 것 고려해줌
        if len(path) == len(tickets) + 1:
            answer.append(path)
            return
        for idx, ticket in enumerate(tickets):
            #아직 방문한적 없고 출발지가 이전의 도착지와 같다면
            if ticket[0] == pre and not visited[idx]:
                visited[idx] = True
                dfs(ticket[1], path + [ticket[1]])
                #가능한 경로가 두가지이상일 때 고려해줌
                visited[idx] = False
                
    dfs("ICN",["ICN"])
    return answer[0]

 

 

배운점

 

사실 dfs 보다는 bfs 가 더 익숙해서 dfs를 응용하는 방법을 잘 몰랐는데 이 문제를 통해서 문제의 조건에 맞게 dfs 알고리즘을 적절히 변형하여 적용시키는 방법에 대해서 배우게 되었다.

 

 

그리고 

 

#가능한 경로가 두가지이상일 때 고려해줌
 visited[idx] = False

 

이 부분이 왜 가능한 경로가 2가지이상일 때를 고려해주기 위한 코드인지 이해가 안될 수 있는데 밑의 예시를 보면 쉽게 이해할 수 있다.

 

ICN -> AAA
ICN -> BBB
AAA -> ICN

 

이렇게 경로가 주어져있다고 할때

1. ICN에서 출발하여 AAA로 가는 경로를 탐색합니다.
   • visited 리스트는 [True, False, False] 상태가 됩니다.
   • 경로는 ["ICN", "AAA"]가 됩니다.
2. A에서 다시 ICN으로 돌아가는 경로를 탐색합니다.
   • visited 리스트는 [True, False, True] 상태가 됩니다.
   • 경로는 ["ICN", "AAA", "ICN"]가 됩니다.
3. 이제 ICN에서 BBB로 가는 경로를 탐색할 차례입니다. 이때, 이전에 사용한 티켓 ICN -> AAA를 다시 사용할 수 있도록 visited[idx] = False를 통해 상태를 되돌립니다.
   • visited 리스트는 [False, False, True] 상태가 됩니다.
   • 경로는 ["ICN"]로 되돌아갑니다.
4. ICN에서 B로 가는 경로를 탐색합니다.
   • visited 리스트는 [False, True, True] 상태가 됩니다.
   • 경로는 ["ICN", "BBB"]가 됩니다.