프로그래머스 코딩테스트 고득점 Kit_DFS/BFS_여행경로

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

해당 문제에서 알파벳 순서가 앞서는 경로를 return 해야 함에 주의한다.
=> graph = {출발 공항 : [도착 공항1, ...]..}
다음과 같은 형태로 항공권을 사용하여 그래프를 인접리스트 형태로 구현한다.

단, 인접한 노드들 중 알파벳 순서가 앞서는 노드를 먼저 방문해야 하기 때문에 인접리스트를 내림차순으로 정렬시키고, 다음으로 방문할 노드를 pop()한다.
( pop()은 항상 맨 왼쪽(인덱스 -1)에서 이뤄짐으로 내림차순하면 가장 알파벳 순서가 앞서는 노드를 선택한다.)

그래프를 DFS순회하며 한 브런치의 가장 높은 레벨까지 내려간 뒤, 다시 벗어나며 route에 노드를 추가한다.
=> route에는 경로가 거꾸로 저장 됨으로 return route[::-1] 하여 저장했던 경로를 뒤집어준다.

구현 코드 (recursion)👇

from collections import defaultdict
def solution(tickets):
    #티켓 내림차순 정렬 
    tickets.sort(reverse = True)
    
    #그래프 인접리스트 형태로 표현
    graph = defaultdict(list)
    for start, end in tickets:
        graph[start].append(end)
    
    route = [] #경로를 담을 리스트 (마지막부터 처음까지 거꾸로 담김)
    
    #DFS(recursion구현)
    def dfs(start):
        while graph[start]:
            dfs(graph[start].pop())
        route.append(start)
    
    dfs('ICN') #'ICN에서 출발'
    
    return route[::-1]

구현 코드 (stack)👇

from collections import defaultdict

def solution(tickets):
    #티켓 내림차순 정렬 
    tickets.sort(reverse = True)
    
    #그래프 인접리스트 형태로 표현
    graph = defaultdict(list)
    for start, end in tickets:
        graph[start].append(end)
    
    #DFS(stack 구현)
    route, stack = [], ['ICN'] #경로를 담을 리스트 (마지막부터 처음까지 거꾸로 담김)
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        route.append(stack.pop())
    
    return route[::-1]