프로그래머스 43164 여행경로 파이썬 풀이

난이도 : Lv. 3

풀이일 : 2411144

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

프로그래머스

---

문제

---

풀이 코드

def solution(tickets):
    answer = []
    visited = [False] * len(tickets) # 방문여부
    
    def DFS(route):
    	# 모든 티켓을 사용했다면 route에 경로 추가
        if len(route) == len(tickets) + 1:
            answer.append(route)
            return
            
 	# 현재 위치에서 이동 가능한 곳으로 티켓 사용
        for i in range(len(tickets)):
            if tickets[i][0] == route[-1] and not visited[i]:
                visited[i] = True # 티켓 사용 표시
                DFS(route + [tickets[i][1]]) # 다음 목적지 추가
                visited[i] = False
        return
    
    DFS(['ICN'])
    answer = min(answer) # 알파벳순으로 가장 빠른 경로
    
    return answer

• answer : 가능한 모든 경로를 담을 배열, 마지막에 알파벳순으로 앞서는 경로 하나만 저장한다.
• visited : 각 탐색에서 티켓의 사용 여부를 확인하기 위한 boolean 배열
• DFS
  • 현재 모든 티켓을 사용했다면, answer에 현재 경로를 추가한다. 이 때, 티켓 정보가 출발지 - 도착지로 되어있으므로 route는 tickets의 길이보다 1 커야 모든 티켓을 사용해 도시를 방문했는지 확인이 가능하다.
  • 아직 모든 티켓을 사용하지 않았다면, tickets를 순회하며, 현재 위치에서 방문할 수 있는 목적지를 찾는다. 찾은 후에는 티켓 사용 여부를 확인하고, 해당 티켓을 사용처리 한 다음, 다음 DFS를 호출한다.
• DFS(['ICN']) : 출발지는 고정되어 있으므로, 처음 도시를 넣고 DFS 탐색을 진행한다.

---

느낀점

• BFS는 익숙한데, DFS는 별로 익숙하지 않은 것 같다. 둘다 가능하면 한동안 DFS로 풀어봐야지.
• 처음에는 저 도시들 간 연결을 따로 저장해두고 사용하려고 했는데, 그냥 tickets 사용여부를 검사하며 순회해도 시간이 괜찮았다.