여행경로 *

여행경로
깊이/너비 우선 탐색(DFS/BFS)
2586명 완료

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

코딩테스트 연습 - 여행경로

시간을 고려하지 않고 문제를 풀겠습니다. 

def solution(tickets):
    from itertools import permutations
    answer = []
    for path in permutations(tickets):
        temp = ['ICN']
        for ticket in path:
            if ticket[0] == temp[-1]:
                temp.append(ticket[1])
            else:
                break
        else:
            answer.append(temp)
    return sorted(answer)[0]

당연히 시간제한이 걸리겠죠.. ^^;;

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.05ms, 10.7MB)
테스트 4 〉	통과 (0.04ms, 10.6MB)

직접 순열 알고리듬을 만들고
중간에 조건을 걸어 필터링 해주면 시간이 많이 절약될 것 같습니다. 

예전에 순열 만든 걸 재탕하겠습니다.
https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9

def perm(arr, depth, n, k, answer):
    if depth == 1 and arr[0][0] != 'ICN':
        return
    if depth > 1 and arr[depth - 2][1] != arr[depth - 1][0]:
        return
    if depth == k:
        temp = [arr[i][0] for i in range(n)]
        temp.append(arr[n - 1][1])
        answer.append(temp[:])
        return
    for i in range(depth, n):
        arr[i], arr[depth] = arr[depth], arr[i]
        perm(arr, depth + 1, n, k, answer)
        arr[i], arr[depth] = arr[depth], arr[i]


def solution(tickets):
    answer = []
    perm(tickets, 0, len(tickets), len(tickets), answer)
    return sorted(answer)[0]

테스트 1 〉	통과 (476.86ms, 13.8MB)
테스트 2 〉	통과 (0.02ms, 9.46MB)
테스트 3 〉	통과 (0.02ms, 9.46MB)
테스트 4 〉	통과 (0.04ms, 9.62MB)

다행히 통과.. 레벨3부터는 잘 풀자보다 통과라도... 라는 생각이..

 

제가 소개한 순열도 깊이 우선 검색을 바탕에 깔고 있지만...
마지막에 모아서 정렬하지 말고, 중간 중간 미리 정렬하면 더 빨리 답을 찾을 수 있겠죠?

def solution(tickets, arrived=['ICN']):
    if not tickets:
        return arrived
    next_airports = [index for index, (ap, _) in enumerate(tickets) if ap == arrived[-1]]
    if not next_airports:
        return None
    next_airports.sort(key=lambda x: tickets[x][1])
    for next_airport in next_airports:
        checker = solution(tickets[:next_airport] + tickets[next_airport + 1:], arrived + [tickets[next_airport][1]])
        if checker is not None:
            return checker

테스트 1 〉	통과 (0.10ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)