[프로그래머스 - Python] 여행경로

 

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=python3

프로그래머스

 

문제 요약

항공권 정보가 담긴 배열
방문하는 공항 경로를 배열에 담아 반환
항상 "ICN"에서 출발

주어진 항공권 모두 사용
가능한 경로가 2개 이상인 경우, 알파벳 순서가 앞서는 경로 반환

 

 

코드 설명

answer = []       
def solution(tickets):
    global answer
    
    visited = [0] * len(tickets)
    
    dfs("ICN", ["ICN"], tickets, visited)
            
    answer.sort()
    
    return answer[0]

 

가능한 모든 경로를 dfs 함수를 호출하여 answer 변수에 담고,

여러 경로가 존재할 경우, 알파벳 순으로 앞서는 경로를 출력하여야 함으로

정렬하고 첫 번째 원소를 반환한다.

 

def dfs(airport, path, tickets, visited):
    global answer
    
    if len(path) == len(tickets) + 1:
        # 경우가 여러 개인 경우, 알파벳 순인걸 정답으로
        answer.append(path)
        return
        
    for j in range(len(tickets)):
        if tickets[j][0] == airport and visited[j] == 0:
            visited[j] = 1
            dfs(tickets[j][1], path + [tickets[j][1]], tickets, visited)
            visited[j] = 0

 

우선, dfs로 순회하면서 백트래킹을 사용하여 가능한 모든 경로를 탐색한다.

탐색하는 과정에서 모든 공항을 경유한 경우에는 해당 경로를 answer에 저장한다.

 

그렇게 어렵지 않은 dfs+백트래킹 문제이다.

 

 

다만 dfs 함수를 solution 함수 외부에 작성하여, 함수의 인자가 많아짐으로

중첩 함수로 작성하여 간결하게 코드를 작성할 수도 있다.

 

def solution(tickets):
    answer = []
    
    visited = [False] * len(tickets)
    
    def dfs(airport, path):
        if len(path) == len(tickets) + 1:
            answer.append(path)
            return
        
        for idx, ticket in enumerate(tickets):
            if airport == ticket[0] and visited[idx] == False:
                visited[idx] = True
                dfs(ticket[1], path + [ticket[1]])
                visited[idx] = False
            
            
    dfs("ICN", ["ICN"])
    answer.sort()            
    
    return answer[0]

 

 

배운 점

- 간결한 코드 작성을 위해서는, 고정된 값(시작 값)은 초기화 시켜두고 시작하는 것이 좋다.

- 중첩 함수로 작성하면 함수 호출 시, 인자 개수를 줄일 수 있다.