여행경로

• 여행경로

문제 설명

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예ticketsreturn

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

문제가 잘 안풀린다면😢

힌트가 필요한가요? [코딩테스트 연습 힌트 모음집]으로 오세요! → 클릭

코딩테스트 연습 힌트 모음집

 

 

 

문제풀이:

from collections import deque
def solution(tickets):
    answer = []
    
    # ICN 공항에서 항상 출발
    
    
    print(tickets)
    q=deque()
    q.append("ICN")  
    result=[]
    while(q):
        tickets.sort(key=lambda x:(x[0],x[1])) # 0번인덱스가 같은거라면 1번을 알파벳순으로 정렬하기
        start=q.popleft()
        result.append(start)
        for i in range(len(tickets)):
            if tickets[i][0]==start:

                q.append(tickets[i][1])
                tickets[i][0]='pass'
                break
        
    answer=result
    return answer

결과:

테스트 케이스 1번과 2번이 틀렸다. 이유를 보니 비행기가 연결이 안되는부분이 나타나게 됐다.

 

정답

문제풀이 2번: 

 

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

    answer.sort()
    
        
    return answer[0]

 

맨처음에 비행기 start지점 및 비행경로 인덱스 사용여부를 q 에 삽입시킨다.

 

enumerate 함수는 4개의 인덱스가 있다면 1 2 3 4 와 같이 반환을 시켜준다.

 

airport 가 0번인덱스와 같고 인덱스 사용여부를 판단하여 사용하지않은 비행기를 선택한다.

q에 ticket[1] 과 경로를 삽입하고 인덱스여부를 더해준다.

 

맨마지막으로 path를 알파벳순으로 정렬시켜준 후 [0]인덱스를 출력시켜주었다.