[programmers] Lv.3 여행경로 (python)

✏️ 문제

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

🤖 알고리즘

 

#DFS  

 

 

🤯 풀이 방법

 

끝까지 경로를 찾는 거라 DFS를 이용했다.

먼저 알파벳 순서가 앞서는 경로를 찾아야 하기 때문에 항공권을 정렬해주고

인천공항에서 출발하는 경로부터 찾아서 인덱스를 이용해 DFS

현재의 도착 지점에서 출발하는 경우가 있다면 정답 리스트에 넣고 재귀

정답 리스트의 길이가 전체 항공권의 수와 같고, 모두 방문했다면 답에 해당

정렬했기때문에 가장 먼저 나오는 결과가 정답이 됨

처음에는 모두 구했는데, 테스트케이스 1번이 400ms가 나와서 고민하다가

하나라도 완성된 경우 그만 찾게 했더니 0.07ms로 차이가 많이 났다

1번 테케가 전체 다 돌면 오래걸리게 되어있는듯

 

 

 

👾 구현 코드 (파이썬)

 

-- 수정 전

def solution(tickets):
    # DFS: 재귀 (인덱스 사용?)
    # 순서대로 탐색하면서 [0]이 [1]과 같다면 append

    def travel(i, v, l):
        if len(l) == len(tickets) and 0 not in v:
            l.append(tickets[i][1])
            answer.append(list(l))
            return

        for j in range(len(tickets)):
            if v[j] == 0 and tickets[j][0] == tickets[i][1]:
                l.append(tickets[j][0])
                v[j] = 1
                travel(j, v, l)
                v[j] = 0
                l.pop(-1)
                             

    answer = []
    tickets = sorted(tickets)	# 알파벳 순서 빠른대로 탐색해야됨
    for idx, t in enumerate(tickets):
        if t[0] == "ICN":	# 인천공항에서 출발하는 경우 모두 탐색
            visited = [0] * len(tickets)
            lst = ["ICN"]	# 시작점 저장
            visited[idx] = 1
            travel(idx, visited, lst)
                
    return min(answer)

 

-- 수정 후

def solution(tickets):
    # DFS: 재귀 (인덱스 사용?)
    # 순서대로 탐색하면서 [0]이 [1]과 같다면 append

    def travel(i, v, l):
        global check
        if check == 1:
            return 
        
        if len(l) == len(tickets) and 0 not in v:
            l.append(tickets[i][1])
            answer.append(list(l))
            check = 1
            return

        for j in range(len(tickets)):
            if v[j] == 0 and tickets[j][0] == tickets[i][1]:
                l.append(tickets[j][0])
                v[j] = 1
                travel(j, v, l)
                v[j] = 0
                l.pop(-1)


    answer = []
    global check
    check = 0
    tickets = sorted(tickets)	# 알파벳 순서 빠른대로 탐색해야됨
    for idx, t in enumerate(tickets):
        if check:
            break
        if t[0] == "ICN":	# 인천공항에서 출발하는 경우 모두 탐색
            visited = [0] * len(tickets)
            lst = ["ICN"]	# 시작점 저장
            visited[idx] = 1
            travel(idx, visited, lst)
                
    return answer[0]

 

 

 

프로그래머스