[프로그래머스] '여행경로' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 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"]

 

 

알고리즘 분석

 

• 나의 풀이

def bfs(n, country, tickets):
    if (n+1) == len(country):
        return [country]
    if not tickets:
        return []
    answer = []
    for idx, ticket in enumerate(tickets):
        start, destin = ticket
        if country[-1] == start:
            going = bfs(n, country+[destin], tickets[:idx]+tickets[idx+1:])
            if going:
                answer += going
    return answer

def solution(tickets):
    n = len(tickets)
    begin = ["ICN"]

    answer = bfs(n, begin, tickets)
    answer.sort()
    return answer[0]

 

 

• Most1의 풀이 

from collections import defaultdict

def dfs(graph, N, key, footprint):
    if len(footprint) == N + 1:  # footprint의 길이가 N+1과 같다면 
        return footprint 

    for idx, country in enumerate(graph[key]):  # key에 일치하는 graph를 불러옴
        graph[key].pop(idx)  # 참조한 요소는 graph[key]에서 버림

        tmp = footprint[:]  # footprint를 tmp에 copy 
        tmp.append(country)  # tmp에 country 추가
        ret = dfs(graph, N, country, tmp)  # footprint 대신 tmp를 넣고 재귀함수 
        graph[key].insert(idx, country)  # graph[key]의 idx 위치에 country를 추가 

        if ret: # ret에 요소가 있다면 
            return ret # ret 반환 

def solution(tickets):
    graph = defaultdict(list)  # defaultdict(list) : 값을 지정하지 않으면 빈 list로 초기화
    N = len(tickets)  # tickets의 길이

    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])  # defaultdict를 이용해서 리스트 선언 없이 바로 초기화해서 사용
        graph[ticket[0]].sort()

    answer = dfs(graph, N, "ICN", ["ICN"])
    return answer

 

이것도 "단어 변환"이나 "가장 먼 노드"와 같은 방식의 풀이입니다. 

이번에도 이런 방식의 코딩을 목표로 했지만 쉽지 않았네요. 

 

 

• Most2의 풀이 

def solution(tickets):
    def helper(tickets, route): # 재귀함수 
        if tickets == []: # tickets가 빈 리스트라면 
            return route # route 반환 
        # route의 마지막 요소와 tickets[i]의 첫번째 요소가 같다면 i를 새로운 리스트의 요소로 추가
        left = [i for i in range(len(tickets)) if tickets[i][0] == route[-1]]
        if left == []: # left가 빈 리스트라면
            return None # 아무것도 반환하지 않음 
        left.sort(key = lambda i: tickets[i][1]) # tickets를 left의 두번째 요소를 기준으로 정렬

        for next in left: 
        # tickets에서 next번째 요소를 뺀 리스트와 그 요소의 도착지를 추가한 route를 인자로 받는 재귀함수를 실행
            rest = helper(tickets[:next]+tickets[next+1:], route+[tickets[next][1]])
            if rest is not None: # rest가 None이 아니면 
                return rest # rest를 반환 
    return helper(tickets, ["ICN"]) # 재귀함수 helper를 실행 

 

이것 역시 비슷한 방식의 풀이