[프로그래머스 lv3] 여행경로

사용 언어 - Python3

문제 - 여행경로

프로그래머스

 

 

정답

큐를 활용한 BFS 문 (정답 맞춘 여부 X)

q.append(("ICN",["ICN"],[])) = 출발지점airport, 경로path, 지나간 여부used

for idx, ticket in enumerate(tickets)를 활용한다.

ticket 첫번째 값이 airport이고, idx가 지나가지 않았다면, q.append((ticket[1], path+[ticket[1]], used+[idx]))2. 

출발지점을 도착지점으로 바꿔주고, 경로에 도착지점을 추가해주고, idx를 used에 추가해준다.

모든 인덱스를 다 사용했다면, len(used) == len(ticekts)

answer 빈리스트에 지금까지의 경로를 저장한다.

다양한 경로가 있는 경우, sort() 정렬하여 가장 알파벳 순으로 왼쪽에 있는 값을 출력한다. answer[0]

from collections import deque
def solution(tickets):
    answer = []
    q = deque()
    q.append(("ICN",["ICN"],[]))
    
    while q:
        airport, path, used = q.popleft()
        
        if len(used) == len(tickets):
            answer.append(path)
            
        for idx, ticket in enumerate(tickets):
            if ticket[0] == airport and not idx in used:
                q.append((ticket[1], path+[ticket[1]], used+[idx]))
        
    answer.sort()
    return answer[0]

 

 

 

레퍼런스

• 정답 참고

여행 경로 - 파이썬(Python)

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부