[Python][프로그래머스] lv3. 여행경로

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=python3 

프로그래머스

 

내 코드

from collections import defaultdict 

def solution(tickets):
    answer = []
    dic = defaultdict(list)
    tickets.sort(key= lambda x : (x[0], x[1]))
    for [start, end] in tickets:
        dic[start].append(end)
    for k in dic.keys():
        dic[k].sort(reverse=True) 

    def dfs():
        st = ['ICN']
        while st:
            start = st[-1]
            print('start : ', start)
            if not dic[start]:
                answer.append(st.pop())
            else:
                st.append(dic[start].pop())
    dfs()
    return answer[::-1]

 

코드 리뷰

굉장히 어려웠다. 이틀에 걸쳐 끙끙댔지만, 결국 구글링을 열심히 하고 속 시원하게 풀었다. 이 문제를 통해 배운 것들이 많다.

 

defaultdict(list)

dic = defaultdict(list)

여기는 list가 들어갈 수도 있고, int가 들어가거나 tuple 등이 들어갈 수 있다.

int가 들어가면 0부터 초기화가 되어 value의 값을 연산할 수 있다. (+= 1 등으로)

list는 정말 신기하게도, dictionary를 list처럼 사용할 수 있도록 만들어준다.

그래서 이번 문제에서도 비행기의 [출발편, 도착편]이 한 세트로 묶어지는데, 이를 간편하게 풀 수 있도록 도와준다.

defaultdict(<class 'list'>, {'ATL': ['SFO', 'ICN'], 'ICN': ['SFO', 'ATL'], 'SFO': ['ATL']})

그러면 이렇게 정렬된다. 같은 출발편은 싹 다 묶여서 나오는 것이다.

 

lambda (두 개의 변수 사용하기)

tickets.sort(key= lambda x : (x[0], x[1]))

tickets은 앞서 말했듯이 출발편과 도착편이 있다. 이 코드는 출발편이 같을 경우에는 도착 편이 오름차순으로 정렬되게 하려는 의도이다. (먼저 정렬할 값[0], 그 다음 정렬할 값[1])

 

defaultdict 사용

    for [start, end] in tickets:
        dic[start].append(end)
    for k in dic.keys():
        dic[k].sort(reverse=True)

dic을 list처럼 선언하면, 정말 리스트처럼 append를 해주어 값을 추가하면 된다.

tickets은 이차원 배열이므로, 이런 식으로 for문을 돌려서 값을 빼줄 수 있다는 점도 새롭게 알게 되었다.

그리고 dic이 결국엔 dictionary이므로 keys.()를 통해 키값을 기준으로 반복문을 돌릴 수 있다.

키값을 기준으로 reverse 처리하는 것은, stack에 넣을 것이기 때문이다.

stack

stack 에 넣으면 선입선출이 아니라 후입선출이기 때문에 ['ICN', 2] ['ICN',1] 이 있다면 2부터 들어가고, 그 다음 1이 들어간다. 그리고 1이 맨 위에 있으니까 DFS에서 1을 먼저 불러와서 실행하고, 그 다음 2를 실행하게 된다.

 

DFS

 def dfs():
        st = ['ICN']
        while st:
            start = st[-1]

그래서 ICN부터 시작해주는데, 시작하는 방법은 이렇다. 스택에 먼저 'ICN'을 넣어놓고 while문을 실행시킨다.

그리고 st[-1]을 통해 빼내지는 않고, 맨 위의 값(ICN)을 가져와서 start 변수에 넣어준다.

	if not dic[start]:
                answer.append(st.pop())
            else:
                st.append(dic[start].pop())

만약 dic['ICN'] 이라면 'ICN': ['SFO', 'ATL'] 이렇게 있을 것이다. 여기서 하나를 뽑아서 답에 추가해준다. 

만약 존재하지 않는다면, 그곳은 도착지니까 answer에 넣는다.

만약 존재한다면 도착지이자 출발지인 곳이므로 st에 넣고 start에 다시 해당 도착지가 출발지로서 들어갈 수 있도록 한다.