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

풀이 1

deq에 넣어가며 하나씩 빼면서..

from collections import deque
def solution(tickets):
    ticketDeq = deque(tickets)
    deq = deque(["ICN"])
    answer = ["ICN"]

    while ticketDeq:
        start = deq.popleft()
        for s, f in ticketDeq:
            if s == start:
                deq.append(f)

        mini = min(deq)
        deq.clear()
        ticketDeq.remove([start, mini])
        deq.append(mini)
        answer.append(mini)

    return answer

풀이 틀림.

 

풀이 2

조심해야 할 점이 있었습니다.

중복된(같은 이름의) 티켓이 여러 장 들어갈 수도 있다는 것.

from collections import deque
def solution(tickets):
    deq = deque(["ICN"])
    answer = ["ICN"]

    while tickets:
        start = deq.popleft()
        for s, f in tickets:
            if s == start:
                deq.append(f)

        mini = min(deq)
        deq.clear()
        deq.append(mini)
        answer.append(mini)

        for i in range(len(tickets)):
            if [start, mini] == tickets[i]:
                del tickets[i]
                break

    return answer

근데 왜 또 안됨?

 

풀이 3

중간에 끊기는 경로가 존재할 수 있음에 유의하여

DFS로 구현.

 

from collections import deque
def solution(tickets):
    ticket = {}

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

    # 도착지 알파벳순 정렬
    for i in ticket.keys():
        ticket[i].sort()

    deq = deque(["ICN"])
    answer = []

    while deq:
        top = deq[-1]

        if top not in ticket or len(ticket[top]) == 0:
            answer.append(deq.pop())
        else:
            deq.append(ticket[top][0])
            del ticket[top][0]

    return answer[::-1]