[탐색] 여행 경로 (python)

문제 설명

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

프로그래머스

문제 풀이

• BFS/DFS 중에서 BFS로 접근
• 경로가 여러개 일 경우 알파벳 순으로 사용하므로 ticket들 정렬
• gr이라는 딕셔너리에 [출발 지역]:[tickets idx] 저장
• 큐에 현재 공항, 이용한 경로, 사용한 티켓 idx 를 담음 
• 이용 경로의 갯수와 티켓+1 이 같으면 종료 (모두 사용한 거니까)
• 딕셔너리에서 키 값이 없는 것을 그냥 꺼내오면 에러가 나서 get으로 걸러내기
• 이 후에는 기본 bfs

소스 코드

from collections import deque

def solution(tickets):
    answer = []
    tickets.sort()
    n = len(tickets)
    gr = dict() 	#[출발점]:[출발점의 tickets idx]
    for i in range(n):
        s,e=tickets[i]        
        if not gr.get(s):
            gr[s]=[]
        gr[s].append(i)
        
    q = deque()
    q.append(("ICN",["ICN"],[])) 	#현재 공항, answer가 될 path, 사용한 티켓 idx 저장
    
    while(q):
        cur, path, ticekt = q.popleft()

        if(len(path)==(n+1)):	# 사용 티켓 수
            answer=path
            break
        if not gr.get(cur):		# INC,BOO   ICN,COO,  COO,ICN  	같은 경우 막기 위한 조건(ICN-BOO부터 사용하면 에러남)
            continue
        for t in gr[cur]:
            if t in ticekt:
                continue
            end = tickets[t][1]
            q.append((end,path+[end],ticekt+[t]))
    return answer


print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "SFO"], ["ATL","ICN"]]))