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

처음에 dfs로 풀었는데 틀렸다는 결과가 나왔다.

def dfs(search):
    global answer

    if len(graph[search]) == 0:
        return

    new_search = graph[search].pop()
    answer.append(new_search)
    dfs(new_search)


def solution(tickets):
    global graph
    global answer
    answer = []
    graph = defaultdict(lambda: [])

    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])

    # 알파벳 순서로 접근을 하기 위해
    for k, v in graph.items():
        v.sort(reverse=True)

    answer.append("ICN")
    dfs("ICN")
    
    return answer

결국 해설을 보고 차이를 찾아보기로 했다.

https://copy-driven-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-ProgrammersPython-%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C

from collections import defaultdict

def solution(tickets):
    answer = []
    graph = defaultdict(lambda : [])

    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])

    #알파벳 순서로 접근을 하기 위해
    for k,v in graph.items():
        v.sort(reverse = True)

    stack = ["ICN"]

    #모든 행선지를 다 거쳐야 함
    while len(stack) != 0:
        search = stack[-1]

        #만약 더 이상 갈 곳이 없다면 정답 리스트에 저장
        if len(graph[search]) == 0:
            answer.append(stack.pop())
        else:
            #갈 경로가 있으면 알파벳이 낮은 순서대로 방문
            stack.append(graph[search].pop())
    answer.reverse()        
    return answer

내가 착각한 반례가 있었는데
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "SFO"]]
이러한 조건이 있는 경우

dfs로 해결을 시도했을 때는 ["ICN", "ATL", "SFO", "ATL", "SFO"]
결과가 나오게 된다.

stack을 이용한 코드(정답)를 이용했을 때는 ["ICN","SFO", "ATL", "SFO", "ATL"] 결과가 나오게 된다.

문제 조건에서 가능한 경로가 2개 이산일 경우 알파벳 순서가 앞서는 경로를 리턴을 해야 한다는 조건에서 dfs형식으로 구현을 한 것인데 이 점이 틀린 듯 싶다...(물론 다른 점이 틀렸을 수도 있겠지만)

명쾌하게 결론을 짓지는 못하겠으나 해결하면서 2가지 정도를 얻어갈 수 있었다.
1, defaultdict의 사용
2, 간단한 문자열 search는 stack을 사용하면 간결