[DFS] 여행 경로 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3 

코딩테스트 연습 - 여행경로

 

Fact Finding

---

• DFS 문제를 통해 모든 곳을 방문할 수 있는 경로를 저장

Algorithm Flow

---

• Recursion을 통한 DFS 구현 후 경로를 answer에 저장
• start_point 체크를 통해 모든 곳을 방문할 수 없는 경우 filter
• next의 sort과정을 통해 알파벳 우선인 경우를 먼저 탐색

 

구현 코드

## 동일한 티켓이 여러장 있을 수 있다....!
def find_route(arr, now, answer) : 
    if len(arr) == 1 : 
        if len(arr[0]) == 1 : 
            answer.append(arr[0][0])
            return answer, arr
        else : 
            answer.append(arr[0][1])
            return answer, arr
    start_point = []
    for i in range(len(arr)) : start_point.append(arr[i][0])
    if now not in start_point : return answer, arr
    next = []
    for i in range(len(arr)) : 
        if arr[i][0] == now : 
            next.append([arr[i][1], i])
    next = sorted(next)
    for i in next : 
        now = i[0]
        pops = arr.pop(i[1])
        answer.append(now)
        answer, arr = find_route(arr, now, answer)
        if len(arr) == 1 : return answer, arr
        arr.insert(i[1], pops)
        answer.pop()
    return answer, arr

def solution(tickets):
    answer = ['ICN']
    start = 'ICN'   
    answer, tickets = find_route(tickets, start, answer)
    return answer