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

문제

출처

이해

입력

• tickets (항공권 배열)
  • 타입: 배열
  • 크기: 주어지지 않음
  • 원소 (항공권)
    • 타입: 배열
    • 형태: [str1, str2]
    • 의미: str1 공항에서 str2 공항으로 가는 항공권

출력

• 주어진 모든 항공권을 사용할 때 방문하는 공항 경로의 배열

조건

1. 공항의 수는 3개 이상 10000개 이하이다.
2. 모든 도시를 방문할 수 없는 경우는 주어지지 않는다.
3. 가능한 경로가 여러 개인 경우 알파벳 순서가 앞서는 경로를 찾는다.
4. 항상 “ICN” 공항에서 시작한다.

예시

입력:
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]

출력:
["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

접근

문제에서 주어진 조건대로 모든 항공권을 사용하는 경로를 탐색하면 된다. 그런데 처음으로 발견한 모든 항공권을 사용할 수 있는 경로가 조건 3을 바로 만족시킬 수 있는 방법이 있다. 애초에 알파벳 순으로 경로를 탐색하는 것이다. 구체적으로 설명하면 어떤 공항을 방문했을 때, 해당 공항에서 방문할 수 있는 공항을 알파벳 순으로 정렬하고 DFS로 탐색하면 된다.

구현

DFS

def solution(tickets):
    """
    tickets_cnt[(A, B)]: A 공항에서 B 공항으로 가는 항공권의 수
    routes[A]: A 공항에서 갈 수 있는 공항 배열
    answer: 현재 방문 경로
    """
    tickets_cnt = {k: 0 for k in map(tuple, tickets)}
    routes = {k: [] for k in set(sum(tickets, []))}
    answer = []

    for src, dst in tickets:
        tickets_cnt[(src, dst)] += 1
        routes[src].append(dst)

    for k in routes.keys():
        routes[k].sort()

    def dfs(now):
        if not any(tickets_cnt.values()):
            return answer
        for nxt in routes[now]:
            if tickets_cnt[(now, nxt)] > 0:
                tickets_cnt[(now, nxt)] -= 1
                answer.append(nxt)
                if dfs(nxt):
                    return answer
                answer.pop()
                tickets_cnt[(now, nxt)] += 1

    return ['ICN'] + dfs('ICN')

또는

def solution(tickets):
    """
    routes[A]: A 공항에서 갈 수 있는 공항 배열
    answer: 현재 방문 경로
    """
    routes, answer = dict(), []
    
    for src, dst in tickets:
        routes[src] = routes.get(src, []) + [dst]
        routes[dst] = routes.get(dst, [])
        
    for v in routes.values():
        v.sort()
    
    def dfs(now):
        if len(answer) == len(tickets):
            return answer
        for nxt in routes[now]:
            routes[now].remove(nxt)
            answer.append(nxt)
            if dfs(nxt):
                return answer
            answer.pop()
            routes[now].append(nxt)
            routes[now].sort()

    return ['ICN'] + dfs('ICN')

덜 직관적이지만 메모리를 아낄 수 있는 구현도 있다. 단, for in으로 도는 중인 iterator를 조작하게 되면 실수하기 쉽고 디버깅이 어려워지 때문에 권장하지 않는 방법이다.