[프로그래머스] 여행 경로 (Python)

문제

문제 링크

문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명
예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

문제 해결 접근

• 처음에는 dfs 재귀 함수로 모든 경로를 완전하게 탐색해본 뒤, 정렬을 해서 조건에 맞는 경로를 최종적으로 리턴하고자 했다.
• 그러나 그 부분에서 계속 오류가 났고, 여러 반례 케이스를 통과했음에도 불과하고!! 테케 1에서 불통을 받았다.
• 계속 기존 코드를 수정하다가 답이 안나와서, 다른 사람의 풀이를 확인하여 stack를 이용하여 간결하게 푸는 코드를 사용했다.
  
  

코드 구현

trial 1 (fail)

def dfs(d, a, idx, visited, tickets, answer):
    
    ## 종료 조건 
    if 0 not in visited:
        answer.append(a)
        if (len(answer) == len(tickets)+1): ## 모든 티켓이 사용되었고, 모든 공항을 방문했다면 
            ans.append(answer)
            return
    
    ## 다음 지점 후보 선택
    for new_idx, (new_d, new_a) in enumerate(tickets): 
        if visited[new_idx] == 1: continue
        if a == new_d:
            answer.append(new_d)
            visited[new_idx]=1
            dfs(new_d, new_a, new_idx, visited, tickets, answer)
            visited[new_idx]=0
            answer=answer[:-1]

def solution(tickets):
    global ans
    
    ans = []
    for idx, (d, a) in enumerate(tickets): ## 시작 지점 후보 선택
        if d == "ICN":
            answer = []
            answer.append("ICN")
            visited = [0] * len(tickets) ## 항공권을 사용했는지 확인
            visited[idx] = 1
            dfs(tickets[idx][0], tickets[idx][1], idx, visited, tickets, answer)
            visited[idx]=0
    return min(ans)

• 먼저 시작지점 후보를 선택하고, 그 후보로부터 dfs를 돌린다.
• dfs를 진행하는 동안 모든 티켓이 사용되었고, 모든 공항을 방문했다면 ans에 넣도록 하고 (종료조건)
• dfs를 마무리하고 돌아왔을 때는 visited와 answer를 하나씩 전으로 초기화해서 다음 방문에 확인하도록 하였다.
• 마지막에 ans에 저장된 모든 경로에 대하여, 알파벳 순으로 정렬하여 가장 빠른 것을 반환하도록 하였다.
• 그러나 테스트 케이스 1 번을 계속 통과하지 못했다. 아직도 왜인지 모르겠다 🤔

관련된 힌트 / 반례들을 찾았고, 아래의 것들은 통과했는데 왜 1번 테케는 통과가 안 되는지... 찾다가 결국 못찾았다.

1) 힌트 1

• 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 하는 것은 맞습니다. 그러나 이것이 "ICN"에서 출발하여 무조건 알파벳 순서가 앞서는 곳을 향하도록 여행 경로를 구성하면 문제의 답을 올바르게 구할 수 있음을 보장하지는 않습니다.

tickets	result
[["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]]	["ICN", "CCC", "DDD", "ICN", "AAA", "BBB", "AAA", "BBB"]

• 위 예시에서 처음에 "ICN"에서 출발하여 "AAA"를 먼저 방문한다면 주어진 항공권을 모두 사용하지 못합니다. 대신에 "CCC"를 먼저 방문한다면 항공권을 모두 사용하는 경로를 구성할 수 있습니다.

-> 내 코드에서는 이 케이스가 통과가 된다. 도중에 돌아오지 못하는 경우에는 그 경로는 최종적인 ans에 저장되지 못한다. 그리고 분기점으로 다시 돌아가서 새로운 경로를 탐색할 수 있게 하였다.

2) 힌트 2

• 항공권 [a, b]는 유일하다고 가정했나요?
• 문제에 항공권 정보가 중복되지 않는다는 언급이 없습니다. 동일한 항공권이 여러 장 주어질 수 있음을 감안하고 풀이를 작성해야 합니다.
• 동일한 항공권이 여러 장이더라도 서로 다른 항공권으로 구분해 주세요.

-> visited를 통해 idx로 항공권을 구분하기 때문에 중복되는 항공권도 구분되고 있다고 생각한다.

3) 힌트3

• 재귀 호출을 이용했나요? 빠뜨리고 탐색하지 못한 경로는 없나요?
• 재귀 호출을 이용한 깊이 우선 탐색으로 풀기 좋은 문제입니다. 일반적으로 그래프에서 재귀 호출로 정점들을 방문한다면 함수를 호출하면서 방문 표시한 곳을, 반환될 때는 초기 상태로 돌려놓아야만 모든 경로를 탐색할 수 있습니다.
• 이 문제를 재귀 호출을 이용한 백트래킹 기법으로 풀었다면 마찬가지로 함수를 호출하면서 사용한 항공권을, 함수가 반환될 때에는 다시 사용하지 않은 항공권으로 되돌려야 합니다.

-> visited와 answer를 돌려놓는 것으로 이 부분을 커버했다고 생각했는데, 이 부분이 문제인 것인가?

trial 2 (pass)

def solution(tickets):
    routes = {} ## key: 시작지점, value: 도착 지점 / 갈 수 있는 공항이 있는지 없는지 확인하기 위하여 / 중복 경로도 구분이 됨 
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
        
    for r in routes:
        routes[r].sort(reverse=True) ## 도착 지점들은 알파벳 거꾸로 순서로 정렬 
        
    stack = ["ICN"]
    path = []
    
    while len(stack) > 0:
        top = stack[-1]
        
        if top not in routes or len(routes[top]) == 0: ## 모든 루트를 잘 따라 갔을 때  / 혹은 길을 찾던 도중 더이상 갈 수 있는 공항이 없을 때 
            path.append(stack.pop()) ## stack에서 지우기 / path에 경로를 추가하기 
        else:
            stack.append(routes[top][-1]) ## 다음에 갈 수 있는 공항 중 알파벳이 빠른 순서를 stack에 넣기 
            routes[top] = routes[top][:-1] ## stack에 넣은 공항은 routes에서 제거하기 
    
    return path[::-1]

• 다른 사람의 풀이를 가져와서 주석을 달아서 해결했다.
• 기본적인 아이디어는 routes를 선언하여 갈수 있는 공항이 있는 확인할 수 있는 dictionary를 만들고
• stack을 돌면서, 모든 루트가 성공적으로 끝났을 때나 찾던 도중 갈 수 있는 길이 없을 때는 stack에서 pop하고 path에 넣어준다.
• 그리고 다음에 갈 path에 있을 때는 계속 stack에 그 경로를 쌓아주면서, route에서 그 길들을 지워나간다.

굉장히 깔끔한 코드다! 그러나 작동 원리에 대해서 궁금한 점이 남았다.

1) 더 이상 갈 수 있는 루트가 없을 때 path에 넣어준다. 이후에 다른 갈 수 있는 path들이 stack에 쌓이면 연이어서 path에 넣게 되는데, 이 두 가지의 루트가 서로 연결되는지 어떻게 알 수 있는 것이지?? 그것이 궁금하다.

예를 들어, 위의 힌트1 반례케이스에서의 route는 이렇게 정의된다.

routes: {'ICN': ['CCC', 'AAA'], 'CCC': ['DDD'], 'AAA': ['BBB', 'BBB'], 'DDD': ['ICN'], 'BBB': ['AAA']}

이렇게 'AAA' 먼저 방문을 하면 더이상 다른 공항을 방문할 수 없는 상태가 된다.

***
routes: {'ICN': ['CCC'], 'CCC': ['DDD'], 'AAA': [], 'DDD': ['ICN'], 'BBB': []}
stack: ['ICN', 'AAA', 'BBB', 'AAA', 'BBB']
path: []

그러면 다시 갈 수 있는 상태가 될 수 있을 때 까지 stack에서 pop하고 path에 넣게 되는데,

***
routes: {'ICN': ['CCC'], 'CCC': ['DDD'], 'AAA': [], 'DDD': ['ICN'], 'BBB': []}
stack: ['ICN']
path: ['BBB', 'AAA', 'BBB', 'AAA']

나머지 경로를 모두 찾아서 stack에 넣었을 때, 이 stack을 pop해서 path에 하나씩 넣으면 stack의 마지막인 'ICN'과 path의 마지막인 'AAA'가 서로 연결이 된다. 그러나 연결된다는 보장이 어떻게 생기는 것인지가 궁금하다.

***
routes: {'ICN': [], 'CCC': [], 'AAA': [], 'DDD': [], 'BBB': []}
stack: ['ICN', 'CCC', 'DDD', 'ICN']
path: ['BBB', 'AAA', 'BBB', 'AAA']

느낀 점

• 원래 재귀함수를 잘 못 짰는데,, 그래도 백트래킹짜는 방식에 대해서 조금은 감이 생긴 거 같다. 그러나 왜 테스트 케이스 1번이 통과되지 않는지 너무너무 궁금했다 ㅜㅜ
• stack을 사용해서 푸는 법이 훨씬 더 간결하면서도 직관적이라고 느껴졌다. 다양한 방식의 풀이에 익숙해지면 좋을 것 같다.
• 아직 완벽하게 해결된 것 같지 않아 의문점들이 많이 남아있는데, 이 부분들을 고민해서 해결해나가고 싶다!