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

문제 링크

---

문제 요약

BFS/ DFS 유형 에 해당한다.
문제에서의 조건은 다음과 같다.
1 ) 제공되는 모든 항공원을 사용해야한다.
2 ) 만약 가능한 경로가 2개 이상이라면, 알파벳 순서가 앞서는 경로를 return
3 ) 모든 도시를 방문할 수 없는 경우는 주어지지 않는다.

문제를 파악해보면 모든 경로를 파악하고 가능한 경로를 구해야하기 때문에 DFS 알고리즘을 사용하기로 결정했다.
하지만, 어떤 방식으로 구현해야할지 첫 틀을 잡는데 시간을 소요했던 것 같다.

---

문제 풀이

def solution(tickets):
    answer = []
    isTicket = [0]*len(tickets) # ticket 사용 여부
    
    def DFS(airport, path):
        if len(path) == len(tickets)+1:
            answer.append(path)
            return
        
        for idx, ticket in enumerate(tickets):
            
            if airport == ticket[0] and not isTicket[idx]:
                isTicket[idx] = 1 # 티켓 사용
                #print(path+[ticket[1]])
                # path + [ticket[1]] 방식: path 리스트에 ticket[1]을 추가한 새로운 리스트 반환
                # -> 재귀 함수에서 유용 
                # path.append(ticket[1]) 방식 : 리스트 자체를 수정 
                DFS(ticket[1], path+[ticket[1]])
                isTicket[idx] = 0

    
    DFS("ICN", ["ICN"])
    answer.sort()
    #print(answer)
    
    return answer[0]

---

📌 해결 방법

• BFS/DFS 문제에 해당하고 그 중 DFS를 활용하였다.