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

문제는 여기!

 

안녕하세요! 이번 시간에는 프로그래머스의 연습문제인 "여행경로" 문제 풀이에 대해 포스팅하겠습니다. 문제의 설명이 조금 빈약

저의 머리도 빈약

해서 다른 사람들의 포스팅을 보고 풀이 방법에 대해서 조금 참고하면서 풀었습니다. 그럼 시작할게요!

제한사항 및 주의사항

주어진 공항의 수는 3 이상 10,000 이하 입니다.

tickets의 각 행 [a, b]의 의미 : a 공항에서 b 공항으로 가는 항공권이 있다.

주어진 항공권을 모두 사용해야 합니다.

가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 return 합니다.

풀이전략

인트로에서 말씀드렸듯, 처음에 문제 자체를 올바르게 이해하지 못했습니다. 주어진 모든 항공권을 사용해야 한다라는 의미는 모든 공항을 탐색해야 한다는 의미라고 할 수 있겠습니다. 또한, 문제를 처음 접한 저처럼 알파벳 순서에만 초점을 맞추고 문제를 풀이하게 되면 오답을 리턴합니다. 예를 들어볼게요.

출발	도착
ICN	AAA, BBB
AAA	없음
BBB	ICN

ICN에서 항상 출발합니다. 알파벳 순서대로 AAA로 탐색하게 된다면, AAA에서 다음 목적지로 갈 수 있는 티켓이 없습니다. 모든 공항을 탐색해야하기 때문에 AAA부터 가면 안돼요!

ICN > BBB > ICN > AAA 이렇게 출력해야 정답입니다. 이제 이 과정을 코드로 표현해보겠습니다.

저는 DFS로 풀이했는데요. 티켓을 바탕으로 a(출발지) : [b, ...(도착지들)]의 딕셔너리(route)를 만들었습니다. 그리고 출발지(key)마다 도착지(values)를 역순으로 정렬했습니다. 이유는 뒤에서 설명드릴게요.

이제 ICN부터 출발해보겠습니다. 티켓으로 표현한 딕셔너리(route), 티켓 수(len(tickets)), 스택(이하 stack, 초기 값 = ["ICN"]), 정답 리스트(이하 answer, 초기 값 = [])를 매개변수로 설정했고, 재귀 방식으로 호출하면서 정답 리스트의 크기가 티켓 + 1이 될 때, 정답 리스트에 담긴 경로들을 거꾸로해서 리턴해주는 방식입니다.

정답 리스트의 크기가 티켓 + 1이 되지 않을 경우, stack의 맨 위값(출발지)이 티켓이 있는 경우에는 answer에 stack을 pop해준 값을 집어넣어 줍니다. 그렇지 않은 경우에는 stack에 해당 출발지의 도착지를 pop해주고 stack에 넣어줍니다.

도착지를 왜 역순으로 정렬했나요?

가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 리턴해야합니다. DFS과정에서 스택을 이용하기 때문에 pop할 경우 리스트의 맨 뒤 원소가 pop되기 때문에 역순으로 정렬했습니다.

설명이 좀 장황한거 같아 제가 설정한 표를 바탕으로 과정을 보겠습니다.

초기 상황입니다. ICN이 BBB, AAA를 갈 수 있죠. 역순으로 정렬했기 떄문에 stack에 AAA를 담아줍니다.

자 stack의 맨 위인 AAA는 갈 수 있는 곳이 아무데도 없습니다. 이 때, answer 리스트에 AAA(stack.pop())를 담아줍니다.

다시 ICN으로 돌아오면 BBB가 남아있을 겁니다. 이 BBB를 stack에 넣어주겠습니다.

BBB는 ICN으로 갈 수 있는 티켓이 있기에, ICN을 다시 stack에 담아줍니다.

ICN은 이제 갈 수 있는 곳이 없습니다. answer에 담아줍시다. 그 밑에 있는 BBB, ICN도 더 이상 갈 수 있는 곳이 없기에 모두 answer에 차곡차곡 들어가겠죠?

answer 배열에 이렇게 쌓였습니다. 이걸 역순으로 리턴해주면 우리가 원하는 정답을 리턴해줍니다!

코드

from collections import defaultdict


def dfs(route, n, stack, answer):
    if len(answer) == n + 1:
        return answer[::-1]

    while stack:
        top = stack[-1]
        if top not in route or len(route[top]) == 0:
            answer.append(stack.pop())
            return dfs(route, n, stack, answer)
        else:
            stack.append(route[top].pop())
            return dfs(route, n, stack, answer)


def solution(tickets):
    route = defaultdict(list)
    for a, b in tickets:
        route[a].append(b)

    for key in route.keys():
        route[key].sort(reverse=True)

    return dfs(route, len(tickets), ["ICN"], [])

이렇게 여행경로 풀이를 마치겠습니다. 항상 피드백은 환영합니다!!