[프로그래머스] 파이썬 문제풀이 - 여행경로

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

프로그래머스

첫 풀이

1. 딕셔너리 구조로 그래프를 생성한다

2. 시작점:[도착점] 쌍으로 만든다

3. 도착점의 리스트를 역순으로 정렬한다

4. 스택에 출발점인 ICN을 넣고 나머지 점들을 순회한다

5. 스택이 빌 때까지 아래 과정들을 반복한다

6. 스택에서 top 데이터를 꺼낸다

7. top이 그래프에 없거나 top을 시작점으로 하는 티켓이 없는 경우, 스택에서 꺼내 path에 저장

8. 7번이 아니라면 top을 시작점으로 하는 끝점 중 가장 마지막 장소를 꺼내와 스택에 저장한다

마지막으로 path를 역순으로 만든다

def solution(tickets):
    routes = dict() # 1. 그래프 생성

    for start, end in tickets:
        routes[start] = routes.get(start, []) + [end]  
    
    for r in routes.keys(): # 2. 시작점 - [끝점] 역순으로 정렬    
        routes[r].sort(reverse=True)

    # 3. DFS 알고리즘으로 path를 만들어줌.
    st = ["ICN"]
    path = []
    
    while st:
        top = st[-1]

        if top not in routes or len(routes[top]) == 0:
            path.append(st.pop())
        else:
            st.append(routes[top][-1])
            routes[top] = routes[top][:-1]
    answer = path[::-1]
    return answer

 

 

배운 점

1. 그래프를 구현할때는 필요한 형태에 맞게 자료구조를 생각해 만든다