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

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

출발지와 도착지가 적힌 tickets 리스트가 주어지고, ICN으로부터의 경로를 출력하면 되는 문제이다.
이 때 경로가 2가지 이상이라면, 알파벳 순으로 가는 경로를 출력하면 된다.

우선 나는 출발지 별로 도착지들을 알파벳의 역순으로 리스트를 활용해 기록하였다.
알파벳의 역순으로 기록한 이유는 스택 자료구조를 활용하기 위함인데, 스택은 늦게 들어온 데이터부터 추출된다.
따라서 알파벳의 역순으로 정렬해두고, pop연산을 하면 알파벳 순으로 출력된다.

경로는 위와 같이 저장된다.
첫 번째 행은 출발지 별로 도착지를 알파벳의 역순으로 저장해둔 것을 나타낸다.
두 번째 행은 각각의 공항에서 출발하는 횟수를 기록하였다. (출발지 별로 도착지의 개수라고 생각해도 좋다.)

from collections import defaultdict


def solution(tickets):
    roads = defaultdict(list)
    visited = defaultdict(int)
    for start, end in tickets:
        roads[start].append(end)
        visited[start] += 1
    for road in roads:
        roads[road].sort(reverse=True)
    print(roads)
    print(visited)
    answer = []
    def dfs(node):
        answer.append(node)
        visited[node] -= 1
        x = roads[node].pop()
        if visited[x] > 0:
            dfs(x)
        else:
            answer.append(x)
    dfs('ICN')
    print(answer)
    return answer

해당 코드를 돌리면 테스트 케이스 2개는 통과한다.
하지만 막상 제출하려고 하니, 2개의 테스트케이스에서 통과하지 못하고 50점의 점수를 받게 되었다.

from collections import defaultdict


def solution(tickets):
    path = []

    # 1. {시작점: [도착점리스트]} 형태로 그래프 생성
    graph = defaultdict(list)
    for (start, end) in tickets:
        graph[start].append(end)

    # 2. 도착점 리스트를 역순 정렬
    for airport in graph:
        graph[airport].sort(reverse=True)

    # 3. 출발지는 항상 ICN이므로 stack에 먼저 넣어두기
    stack = ["ICN"]
    # 4. DFS로 모든 노드 순회
    while stack:
        # 4-1. 스택에서 가장 위의 저장된 데이터 꺼내오기
        top = stack.pop()

        # 4-2. top이 그래프에 없거나, top을 시작점으로 하는 티켓이 없는 경우 path에 저장
        if top not in graph or len(graph[top]) == 0:
            path.append(top)
        # 4-3. top을 다시 스택에 넣고 top의 도착점 중 가장 마지막 지점을 꺼내와 스택에 저장
        else:
            stack.append(top)
            stack.append(graph[top].pop())

    # 5. path를 뒤집어서 반환
    return path[::-1]

구글링을 통해 참고한 정답 코드이다.
내가 이해할 수 있게끔 코드를 조금 수정한 부분이 있다.

그래도 조금은 이해가 안되어서 어렵다. ㅜㅜ