프로그래머스_여행경로

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

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

 

• 접근법

티켓이 주어질 때, 주어진 티켓을 모두 사용하여 모든 공항에 방문하여야 한다. 

문제를 보자마자 dfs(깊이 우선 탐색)으로 풀어야겠다는 생각이 들었다.

다른 풀이방법도 많지만 전형적인 dfs로 풀어보았다.

 

from collections import defaultdict

def solution(tickets):

    tickets = sorted(tickets, key = lambda x : x[1])
    
    ticket = defaultdict(list)

    for from_, to_ in tickets :
        ticket[from_].append([to_, 1])

    flag = 0
    answer = []
    def dfs(airport, cnt, path) :
        nonlocal flag
        if flag == 1 :
            return

        elif cnt == len(tickets):
            flag = 1
            answer.append(path.split(' '))
            return

        for i in range(len(ticket[airport])) :
            destination = ticket[airport][i][0]
            check = ticket[airport][i][1]
            if check == 1 :

                ticket[airport][i][1] = 0
                dfs(destination, cnt+1, path + " " + destination)
                ticket[airport][i][1] = 1

    dfs('ICN', 0, 'ICN')
    
    return answer[0]

 

• 코드 설명

- 문제의 조건은 주어진 티켓을 모두 사용하는 것이다. 입국은 여러번 하지만 출국은 없는 공항의 경우도 있음을 유의하여야 한다.

- 출력 조건을 보면 가능한 경로가 2가지 이상이면 알파벳 순서가 앞서는 경우를 return하라고 한다. 알파벳 순서가 앞으로 오는 경우를 위해 입력받은 tickets 배열의 2번째 값(목적지) 순으로 오름차순 정렬한다.

- 입력에서 주어진 티켓을 바탕으로 모든 공항에 대해 목적지, 티켓 사용 여부를 저장하는 딕셔너리를 defaultdict()를 이용해 생성했다. (ticket) (사용 가능 : 1, 사용 불가 : 0)

- 출발지는 항상 'ICN'이라고 조건에서 주어지므로 dfs의 시작지점은 'ICN'으로 한다.

- 찾을 수 있는 경로가 여러가지여도 사전에 목적지를 기준으로 오름차순 정렬을 해놓았기 때문에 가장 처음에 구한 경로가 정답이되고 첫번째 정답을 찾은 이후에는 dfs를 빠져나오도록 한다. (flag 사용)

    -> 첫번째 정답을 찾은 경우는 cnt(티켓 사용 횟수)가 전체 티켓 배열의 길이일 때(입력 조건이 모든 경로를 갈 수 있도록 주어진다)

- dfs에서는 위에서 생성한 defaultdict배열 ticket을 참조하여 현재 공항인 airport에서 갈 수 있는 경로를 다음 경로로 넘겨주도록 한다.

- 현재까지의 경로를 저장하는 path는 문자열이다. 다음 경로로 넘어갈 때에는 현재까지의 경로 + 공백 + 다음 경로로 하여 정답을 찾고난 뒤 split을 이용하여 배열화 하였다. 물론 모든 경로를 배열에 담아서 append하는 형식으로도 가능하다.