[코딩테스트] 프로그래머스 - 여행경로 (Lv.3) in Python

flight ticket 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때,

방문하는 공항 경로를 배열에 담아 return.

 

프로그래머스 강의를 바탕으로 풀이했습니다.

 

programmers.co.kr/learn/courses/30/lessons/43164

 

 

풀이

1.

- 개념으로만 알고 있던 깊이우선탐색 (DFS)과 너비우선탐색(BFS) 활용에 대해 감 잡을 수 있었던 문제.

 

중요한 것은,

 

깊이우선탐색(DFS) - 다음 node로 갔다가 진행할 곳이 없으면 바로 그 전 node로 돌아와야 하므로, STACK이 유용

너비우선탐색(BFS) - 각 level의 node들을 모두 방문한 후, 다음 level의 node를 순차적으로 방문해야하므로, 선입선출의 QUEUE가 적절

 

- 그리고 이 문제는 한붓그리기

~> 모든 노드를 탐색

~> 연결된 노드들을 타고 쭉 탐색

의 문제와 같으므로, 깊이우선탐색법을 활용하는 것이다.

 

 

2.

- 항공표들은 출발지를 key, 도착지를 value로 하는 dictionary로 만듦.

- 스택과 리스트 하나씩 준비.

- 스택에는 탐색이 끝나지 않은 도시들을 넣고 (깊이우선탐색을 위함)

- 리스트에는 이미 탐색이 끝난 도시들 - dictionary[key]가 없거나 길이가 0일 때 - 을 넣는다.

- 도시들의 탐색이 모두 끝나면, 리스트에 스택에 있는 도시들을 pop하여 순서대로 이어붙인 후,

- 역순으로 리스트의 도시들을 배열하면 그것이 원하는 결과가 될 것.

 

파이썬 코드 구현

 

def solution(tickets):
    # tickets to dictionary
    dic = {}
    
    for i in tickets:
        dic[i[0]] = dic.get(i[0],[]) + [i[1]]
        
    # sort the destinations by the reverse-alphabetical order
    # reverse because popping an element from a list at its end
    # is more efficient - no additional sorting required
    for r in dic:
        dic[r].sort(reverse = True)
        
    # stack and list initialization
    stk = ["ICN"]
    itinerary = []
    
    while len(stk) > 0:
        top = stk[-1]
        if top not in dic or len(dic[top]) == 0:
            itinerary.append(stk.pop())
        else:
            stk.append(dic[top].pop())
            
    return itinerary[::-1]

 

- 그림을 그려 simulation을 먼저 해보니 훨씬 문제 접근이 쉬웠다.