[프로그래머스 / 파이썬 풀이] 여행경로

실패코드

from collections import deque

def solution(tickets):
    global answer
    answer = []
    tickets.sort(key = lambda x :(x[1]))
    visited_dic = {}
    tickets_dic = {}
    for i in tickets:
        for j in i:
            if j not in visited_dic.keys():
                visited_dic[j] = []
                tickets_dic[j] = []
    
    for i in tickets:
        tickets_dic[i[0]].append(i[1])
        visited_dic[i[0]].append(0)

    def bfs(a):
        global answer
        answer.append(a)
        q = deque()
        q.append(a)
        while q:
            b = q.popleft()
            for i in range(len(tickets_dic[b])):
                if visited_dic[b][i] == 0:
                    visited_dic[b][i] = 1
                    answer.append(tickets_dic[b][i])
                    q.append(tickets_dic[b][i])
                    break

    bfs('ICN')


    return answer

구현에만 초점을 두고 급하게 한 풀이. 실패의 이유로는 

 

ICN, A
ICN, B
B, ICN

"모든 티켓을 사용하여야 한다.", "사전 상으로 빠른 곳을 먼저 방문한다." 라는 제한 사항이 있는데, 

위의 INPUT의 경우 2번째 규칙에 의해 A를 먼저 방문하여야 할 것 같지만 그렇게 되면 A를 출발지로 하는 티켓이 없어 방문하고자 하는 나라를 모두 방문할 수 없는 예외 케이스가 생긴다. 그렇기 때문에 B를 먼저 방문해야 한다.

 

정답코드

def solution(tickets):
    tickets.sort(reverse=True) # 정렬
    routes = dict() # {} 생성
    #그래프 생성
    for t1, t2 in tickets:
        if t1 in routes:
            routes[t1].append(t2)
        else:
            routes[t1] = [t2]
    
    st = ['ICN']
   	ans = []
    while st:
        top = st[-1]
        # 해당 나라가 graph에 없거나, 해당 나라의 키의 값이 0이면 (더 갈데가 없다는 뜻)
        if top not in routes or len(routes[top])==0:
            ans.append(st.pop()) # 해당 나라를 빼서 답안에 넣는다
        else: # 아니면 더 갈 곳을 찾는다 (해당 나라의 키의 값을 stack에 넣음)
            st.append(routes[top].pop())
    ans.reverse()
    return ans