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

프로그래머스_여행경로

문제를 봤을 때 숫자가 아닌 문자로 된 그래프를 그리려니 막막하더라. 숫자 그래프랑 똑같이 DFS를 쓰면 되는데..결국은 다른 분의 풀이 를 참고했다

다른 분도 DFS로 풀리기는 했지만, 한 테스트케이스가 시간이 너무 오래 걸려서 더 좋은 코드를 발견하셨길래 두 가지 모두 시도해봤다

1) 1차 시도

from collections import defaultdict
def solution(tickets):
    graph = defaultdict(list)
    visited = defaultdict(list)
    n = len(tickets)+1
    answer = []
    
    for start, end in tickets:
        graph[start].append(end)
        visited[start].append(False)
        
    def dfs(now, path):
        if len(path)==n:
            answer.append(path)
            return
        
        for j in range(len(graph[now])):
            if not visited[now][j]:
                tmp = graph[now][j]
                visited[now][j] = True
                dfs(tmp, path+[tmp])
                #print(path+[tmp])
                visited[now][j] = False
    
    start = "ICN"
    for i in range(len(graph[start])):
        nxt = graph[start][i]
        visited[start][i] = True
        dfs(nxt, [start, nxt])
        visited[start][i] = False
    
    answer.sort()
    return answer[0]

2) 2차 시도

from collections import defaultdict
def solution(tickets):
    graph = defaultdict(list)
    answer = []
    
    for start, end in tickets:
        graph[start].append(end)
    
    #알파벳이 빠른 순으로 뒤에서부터 pop 할 수 있도록 reverse sort
    for key in graph.keys():
        graph[key].sort(reverse=True)

    
    stack = ["ICN"]
    while stack:
        top = stack.pop()
        # 더이상 갈 수 없다면 answer에 append, 즉 경로의 끝 부분부터 answer에 들어가게 된다
        if top not in graph or not graph[top]:
            answer.append(top)
        else:
            stack.append(top)
            stack.append(graph[top].pop())
    
    return answer[::-1]

어려워보인다고 해서 지레 겁먹지 말고 달려들고 풀어보자!