[Python] 여행경로

1. 문제

 

 

 

 

2. 풀이 과정

방법 1) BFS

from collections import deque
def solution(tickets):
    answer = []
    
    #티켓을 출발점을 key로 저장
    hash_map = {}
    for a, b in tickets:
        if a in hash_map:
            hash_map[a].append([a, b])
        else:
            hash_map[a] = [[a, b]]
    
    def bfs(start):
        q = deque()
        #출발하는 지점의 티켓 넣기
        for h in hash_map[start]:
            q.append([h])

        while q:
            arr = q.popleft()
            #모든 티켓을 사용할 수 있는 경우 답에 추가
            if len(arr)==len(tickets):
                temp = start
                for j in arr:
                    temp = temp +" "+j[1]
                answer.append(temp)
                continue
            #
            if arr[-1][1] in hash_map:
                for a in hash_map[arr[-1][1]]:
                	#같은 티켓 고려 : 선택한 티켓 중의 개수와 주어진 티켓 중의 개수 비교
                    if hash_map[arr[-1][1]].count(a) > arr.count(a):
                        q.append(arr+[a])
                        
    bfs("ICN")
    answer.sort()
    return answer[0].split()

 

방법 2) DFS, 알파벳 순으로 정렬하고 시작하고 깊이 우선으로 보기 때문에 위의 방식보다 더 효율적이다.

from collections import defaultdict
def solution(tickets):

    #list에 key가 없으면 기본(default)으로 빈 리스트로 세팅해줌
    ticket_book = defaultdict(list)
    
    for s, e in tickets:
        ticket_book[s].append(e)
        ticket_book[s].sort() #알파벳 순으로 먼저 방문해보기

    def dfs(book, road):
        if len(road) == len(tickets)+1:
            return road
        
        for idx, r in enumerate(book[road[-1]]):
            #road의 마지막 인자가 다음 티켓 출발점
            e = book[road[-1]].pop(idx)
            answer = dfs(book, road+[e])
            #답 찾으면 더 안보고 return, 알파벳 순으로 정렬해놨기 때문
            if answer:
                return answer
            book[road[-1]].insert(idx, e)
    
    return dfs(ticket_book, ["ICN"])