[프로그래머스] 여행경로

 

 

내가 풀었던 방식으로 했을때는 테스트 케이스 1번과 2번에서 문제가 발생했다.

ex) 

tickets=[['ICN' ,'AAA'], ['ICN', 'BBB'] ,['BBB','ICN']]

답 : ['ICN', 'BBB', 'ICN', 'AAA']

이렇게 나와야하는데, 나의 방식은 ['ICN', 'AAA', 'ICN', 'BBB']로 나온다.

이 방법의 문제점은 AAA에서 출발하는 노선이 없다는 것. 따라서 저 방법은 성립하지 못한다.

 

 

나의 풀이

def solution(tickets):
    answer=[]
    tickets.sort(key=lambda x:(-(x[0]=='ICN'),x[1]))

    index=0
    answer.append(tickets[0][0])

    while True:
        if len(tickets)==0:
            break
        de, en = tickets[index]
        answer.append(en)
        tickets.__delitem__(index)
        for i in range(len(tickets)):
            if tickets[i][0]==en:
                index=i
                break

    return answer

 

고친 풀이 1 (스택사용)

def solution(tickets):
    answer=[]
    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']
    print(routes)

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

    answer.reverse()

    return answer

 

고친 풀이 2 (DFS 사용)

def dfs(graph, N, path, here):
    path.append(here)

    if len(path)==N+1:
        return True

    if here not in graph:
        path.pop()
        return False

    for i in range(len(graph[here])):
        there=graph[here][-1]
        graph[here].pop()

        if dfs(graph,N,path,there):
            return True

        graph[here].insert(0,there)

    path.pop()
    return False

def solution(tickets):
    answer=[]

    routes=dict()

    for (start, end) in tickets:
        routes[start]=routes.get(start,[])+[end]

    for r in routes.keys():
        routes[r].sort(reverse=True)

    N=len(tickets)
    path=[]

    if dfs(routes, N, path, 'ICN'):
        answer=path

    return answer