[Algorithm] 여행 경로

프로그래머스 여행 경로 문제

: 한번에는 못풀었는데, 이유는 문제를 제대로 이해하지 못해서이다..

문제 해석

: 항공권 티켓(왕복이 아닌 편도행)이 tickets로 주어지는데, 그러한 항공권 티켓을 바탕으로 '여행 경로'를 짜야한다. 이 때, 티켓은 반드시 ICN에서 출발해서 비행기를 타고, 타고, 타서 어딘가에 도착할 수 있도록 주어진다. 즉, 중간에 항공권이 없어서, 달리 말해, A->B->C로 갈 때, A->B 항공권이 없고 그런 상황은 없다라는 것. 완벽하게 주어졌다라는 것이다. 그래서 편도행 티켓을 바탕으로 여행 경로를 순서대로 배열에 받아서 리턴하는 것이 문제의 요구사항이다. 이 때, 가능한 여행 경로가 2개 이상이면 공항을 사전순으로 생각했을 때 앞에 배치되는 단어에 해당하는 공항을 먼저 가는 것으로 한다.

내가 놓친점

• 사전순으로 앞선 공항을 먼저 간다는 조건을 너무 쉽게 받아들였다. 본래 의미대로라면 모든 항공권을 쓸 수 있는 여행경로를 찾는 것이 우선이고, 만약 그것을 찾았는데 2개 이상인 경우에 사전순으로 비교를 해서 선택하는 것이었다. 근데, 나는 사전순을 먼저 적용한 케이스다. 애초에 사전순에 역행하는 여행경로는 탐색조차 하지 않아버린 것. 그래서 문제가 됐다.

문제 설계

• DFS+백트랙킹으로 풀면 되는 문제이다. 이 때, 재귀함수를 돌리는데 재귀함수를 호출할 때마다 항공권 티켓을 한장 쓰는 것이므로, tickets 수를 모두 사용한 만큼 재귀함수를 돌리면 기저조건에 해당함으로 시행을 끝낸다. 이 때, 애초에 티켓 정보를 바탕으로 처음부터 공항이름을 사전순으로 정렬해놨기에 바로 시행을 끝낼 수 있는 것.

구현 코드

answer=  ["ICN"]

def recursion(node,d,l):
    global answer
    
    if l == 0:
        return True
    try:
        if d[node]:
            pass
    except:
        return
    
    for idx, airport in enumerate(d[node]):
        answer.append(airport)
        top = d[node].pop(idx)
        
        if recursion(top,d,l-1):
            return True

        d[node].insert(idx,top)
        answer.pop()


    
def solution(tickets):
    d = {}
    
    for el in tickets:
        try:
            d[el[0]].append(el[1])
        except:
            d[el[0]] = [el[1]]
            
    for key, val in d.items():
        val.sort()
        d[key] = val
        
    l = len(tickets)
    root = "ICN"
    recursion(root,d,l)
    
    return answer

코멘트

: 문제를 잘읽자. 계속 풀다보니까 지문이 짧을수록 문제가 그렇게 친절하지 않다. 깊게 파고들어서 이해해야한다.