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

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

코딩테스트 연습 - 여행경로

 

DFS 알고리즘 이용

from collections import defaultdict


def solution(tickets):
    # 특정 티켓의 인접 리스트를 구하는 함수
    # 즉, 도착지가 여러개인 경우를 1가지로 모아줌
    # defaultdict(<class 'list'>, {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})
    def init_graph():
        routes = defaultdict(list)
        for key, value in tickets:
            routes[key].append(value)
            
        return routes
    
    # 주어진 항공권은 모두 사용해야 한다 -> DFS
    # 만약 최단 경로라면 -> BFS
    # 재귀 호출을 사용한 DFS
    def dfs(key, footprint):
        # 모두 방문한 경우라면 방문한 히스토리를 return
        if len(footprint) == N + 1:
            return footprint
        
        # 깊이 탐색을 통해 항공권에서 갈 수 있는 만큼 간다.
        for idx, country in enumerate(routes[key]):
            routes[key].pop(idx)
            
            fp = footprint[:] # deepcopy 같은 얕은 복사
            fp.append(country)
            
            ret = dfs(country, fp)
                      
            # 모든 티켓을 사용해 통과한 경우라면 종료한다.
            if ret:
                return ret
        
            # 모든 도시를 방문하지 못했는데, 더이상 갈 수 없는 경우
            # 해당 도시를 routes에 다시 넣어준다.
            routes[key].insert(idx, country)
        
    routes = init_graph()
    
    # 도착점의 리스트를 알파벳 순서로 정렬함
    for r in routes:
        routes[r].sort()
        
    N = len(tickets)
    answer = dfs("ICN", ["ICN"])
    
    return answer

먼저, 도착지가 여러개인 경우를 1개로 모아주기 위한 인접리스트를 초기화 한다. init_graph() 함수를 통해 각 도시에서 갈 수 있는 항공권의 목록을 모아줄 수 있다.

또한, 이렇게 초기화한 인접리스트의 도착지점을 알파벳 순으로 정렬하여 알파벳 순으로 앞서는 경로를 먼저 택할 수 있게 한다.

 

주어진 항공권을 모두 사용해야 한다는 제약에 힌트를 얻어 DFS 알고리즘을 이용해 구현할 수 있다. (만약 최단경로라면 BFS가 유리할 것)

 

문제 해결 Point

기본적으로 DFS를 통해 재귀적으로 문제를 풀이하면 되지만, 1가지의 경우를 더 고려해야한다.

바로 다음과 같은 경우이다.

[[ICN, BBB], [BBB, ICN], [ICN, AAA]] -> 이 경우에서 ICN -> AAA로 갈 경우, 티켓을 다 사용하지 않았음에도 불구하고 더이상 진행할 수 있는 경로가 없다. 따라서, 이런 상황에서는 방문했던 도시를 다시 넣어주고, 다른 방법을 택해야 한다.

 

굉장히 어려웠던 문제로, 추후에 다시 풀어봐야할 것 같다.