[프로그래머스][python]여행경로

문제

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

소스코드

import collections
def solution(tickets):
        answer = []
        dic = collections.defaultdict(list)
        visited = collections.defaultdict(list)

        for s, e in tickets:
            dic[s].append(e)
            visited[s].append(0)
        for k, v in dic.items():
            dic[k].sort()

        def dfs(l,start,tmp):
            if len(answer) > 0:
                return
            if l == len(tickets):
                answer.append(tmp)
                return

            for i in range(len(dic[start])):
                if not visited[start][i]:
                    visited[start][i] = 1
                    dfs(l+1,dic[start][i],tmp+[dic[start][i]])
                    visited[start][i] = 0

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

        return answer[0]

설명

처음에 문제를 풀었는데 (백트래킹을 안하고 무조건 연쇄적으로 체크함) 테스트케이스1,2 번이 자꾸 틀려서 질문하기에 있는 테스트케이스를 추가해주었다.

BOO가 key일 때 value값을 알파벳 정렬해주면 [AOO,COO] 이렇게 되서 AOO를 탐색하면 모든 경로를 탐색하지 않고 종료해버린다.

그래서 무조건 알파벳 순서로 탐색하는 것이 아닌 백트래킹을 이용해서 모든 경로를 탐색하게 해주었다.

입력

[["ICN", "AOO"], ["AOO", "BOO"], ["BOO", "COO"], ["COO", "DOO"], ["DOO", "EOO"], ["EOO", "DOO"], ["DOO", "COO"], ["COO", "BOO"], ["BOO", "AOO"]]

출력

["ICN", "AOO", "BOO", "COO", "DOO", "EOO", "DOO", "COO", "BOO", "AOO"]

 

1. visited 딕셔너리를 추가해주고 탐색여부를 체크해서 백트래킹을 해준다.

2. dfs를 이용해서 계속 탐색하고 모든 경로를 다 돌면 answer 길이가 티켓 갯수와 같으면 return 한다.

3. 이미 알파벳순서로 도착지를 정렬하고 탐색했기 때문에 가장 먼저 완성된 경로가 정답이다. 그러므로 나중에 추가된 경로는 생각하지 않도록 return 해준다.