프로그래머스, 여행경로

프로그래머스, 여행경로

 

❓문제

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

프로그래머스

 

❓분류

accepted
개발자 친구의 도움을 받았다.
수많은 코드들을 봐도 이해가 안됐는데, 설명들으니 이해된다.
설명 들은 다음 날 스스로 풀어봤다! 시간이 지난 뒤 다시 풀어봐야 할 문제~
모든 티켓을 사용해야 한다는 점이 문제의 풀이법을 생각하는데 핵심!
 

❓ 접근 방법

티켓의 사용여부를 체크해가며 모든 항공권을 사용하는 경로를 저장한다.
만약 해당 항공권을 사용하지 못하는 경우, 이전 출발지로 돌아가 다른 티켓을 사용해 이동한다.(백트래킹)
모든 항공권을 사용하는 경로가 여러개 일 경우 알파벳 순서가 앞서는 경로를 답으로 출력한다.
 

📜 나의 풀이1

from collections import defaultdict

def dfs(city):
    global routes, used, path, N, result

    if len(path) == N + 1:
        # 모든 도시 방문 했다면 result에 해당 경로 저장
        result.append("".join(path))
        return

    if len(routes[city]) == 0:
        # 더 이상 갈 도시 없다면, 예전 위치로 돌아가 티켓 변경
        return

    for i in range(len(routes[city])):
        next_city = routes[city][i]
        if not used[city][i]:
            used[city][i] = True
            path.append(next_city)
            dfs(next_city)
            used[city][i] = False
            path.pop()

def solution(tickets):
    
    # 출발지에서 갈 수 있는 도착지 정보 담고 있는 딕셔너리
    # 각 티켓의 사용여부 표시하는 딕셔너리
    global routes, used, N, result, path
    
    N = len(tickets)
    
    routes = defaultdict(list)
    used = defaultdict(list)
    for start, end in tickets:
        routes[start].append(end)
        used[start].append(False)
    
    path = ['ICN']
    result = []
    
    dfs('ICN')
    # 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
    result = sorted(result)[0]
    
    answer = []
    for i in range(0, len(result), 3):
        answer.append(result[i:i+3])
        
    return answer

 

 

📜 나의 풀이2

from collections import defaultdict

def tour(cur_air, n):
    global total_airport, trip_visit, trip_info, airports, all_routes
    
    if n == total_airport:
        all_routes.append("".join(airports))
        return
    for next_idx in range(len(trip_info[cur_air])):
        next_air = trip_info[cur_air][next_idx]
        if not trip_visit[cur_air][next_idx]:
            trip_visit[cur_air][next_idx] = True
            airports.append(next_air)
            tour(next_air, n+1)
            trip_visit[cur_air][next_idx] = False
            airports.pop()
    
def solution(tickets):
    START_IDX = 0
    SEPARATE_NUM = 3
    
    global total_airport, trip_visit, trip_info, airports, all_routes
    
    trip_info = defaultdict(list)
    trip_visit = defaultdict(list)
    for start, end in tickets:
        trip_info[start].append(end)
        trip_visit[start].append(False)
    
    total_airport = len(tickets)
    airports = ['ICN']
    all_routes = []
    tour('ICN', 0)
    
    all_routes = sorted(all_routes)
    sort_route = all_routes[START_IDX]
    
    answer = []
    for i in range(START_IDX, len(sort_route), SEPARATE_NUM):
        answer.append(sort_route[i:i+SEPARATE_NUM])
    
    return answer