[프로그래머스 Level 3] 여행경로(Python)

📝 Level 3. 여행경로

📌 문제 설명

 

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

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

 

📌 제한사항

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

📌 입출력 예

tickets	return
[["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"] 가 알파벳 순으로 앞섭니다.

 

✏️ 나의 풀이 (BFS 이용)

from collections import deque

def solution(tickets):
    tickets.sort()
    q = deque()
    q.append(['ICN', ['ICN'], []])
    visit = []

    while q:
        start, answer, visited = q.popleft()
        if len(visited) == len(tickets):
            visit.append(answer)
        
        for idx, ticket in enumerate(tickets):
            if idx not in visited and start == ticket[0]:
                q.append([ticket[1], answer+[ticket[1]], visited+[idx]])
    visit.sort()
    return visit[0]

• 가능한 경로가 2개일 경우 알파벳 순으로 간다고 해서 tickets를 sort했는데 오류가 뜬다.. 다른분의 풀이를 참고해본 결과 모든 경로를 visit list에 담은 후 sort하면 0번째 경로로 return하면 정답처리 된다. (이유를 모르겠다..)

 

from collections import deque

def solution(tickets):
    tickets.sort()
    q = deque()
    q.append(['ICN', ['ICN'], []])

    while q:
        start, answer, visited = q.popleft()
        if len(visited) == len(tickets):
            return answer
        
        for ticket in tickets:
            if ticket not in visited and start == ticket[0]:
                q.append([ticket[1], answer+[ticket[1]], visited+[ticket]])

• 위의 코드에서 모든 경로를 저장한 visit가 없을 때 코드(오답코드) ㅠ
  이렇게 제출했을 때 테스트케이스1 에서 오답이 뜬다. 다른분들 글을 봤을 때도 테스트케이스1 때문에 오답이 많이 나오는 것 같은데 이 문제는 나중에 한번 더 확인해봐야겠다!

 

✏️ 다른 풀이(dict, stack 이용)

def solution(tickets):
    answer = []

    routes = {}
    for (start, end) in tickets:
        routes[start] = routes.get(start, []) + [end]

    for r in routes.keys():
        routes[r].sort(reverse = True)

    stack = ["ICN"]
    while stack:
        top = stack[-1]
        if (top not in routes) or (not routes[top]):
            answer.append(stack.pop())  
        else:
            stack.append(routes[top].pop())

    return answer[::-1]

• tickets list를 dict로 한번 정리하고 deque가 아닌 stack을 이용한다. BFS문제를 stack으로도 풀 수 있다는게 특이했다.

 

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

프로그래머스