4. 여행경로 ★★

유형 : DFS

풀이 시간 : 인터넷 검색

 

경로 찾는 문제는 DFS가 훨씬 편한 것 같다는 생각.. 

DFS를 사용할지 BFS를 사용할지도 잘 판단해야 할 듯. 

 

from collections import deque 

def solution(tickets):
    answer = []
    visited = [False] * len(tickets)
    
    #재귀를 이용한 DFS 시작 
    def dfs(curr, path):
    	#종료 조건 : PATH가 완성되었을 경우 
        if len(path) == len(tickets) + 1:
            answer.append(path) #정답 후보 집합에 append
            return
        
        #다음 노드 탐색 (재귀)
        for idx, ticket in enumerate(tickets):
            if ticket[0] == curr and visited[idx] == False:
                visited[idx] = True #우선 방문으로 설정 
                dfs(ticket[1], path + [ticket[1]]) #방문
                visited[idx] = False #만약 유효하지 않은 경로인 경우 다시 탐색 
                
    dfs("ICN", ["ICN"])
    answer.sort()
    return answer[0]

 

1. visited :

  - 한번 방문한 뒤 경로가 실패하면 어떻게 다시 티켓을 유효하게 만들 것인지

  - 장소가 아니라 ticket에 visited를 적용

 

이런 점에서 "재귀" DFS를 사용한는 것이 가장 효율적이었다. 

visited를 방문으로 표시한 후 방문해보고 적용이 안 되었을 경우 다시 방문을 안 한 것으로 표기하기가 간편하다.