[프로그래머스] 여행경로(python 파이썬)

 

갈수 있는 여행 경로를 정하는 문제

dfs로 풀었지만 테스트케이스 1번만 통과가 안된다...

무슨 문젠지 모르겠다.. (질문에 있는 모든 케이스 통과)

1번을 통과하기위해서는 같은 티켓이 여러장 있다고 가정하고 풀면된다고 하는데 고려해서 풀었음에도 통과가 안된다..

(ㅠㅠ 못풀었음)

 

def solution(tickets):
    answer = []

    place = list()
    i = 0
    for ticket in tickets:
        if ticket[0] == 'ICN':
            ticket.append(i)
            place.append(ticket)
        i += 1
    place.sort(key=lambda x: x[1])

    for j in place:
        visited = [False] * len(tickets)
        visited[j[2]] = True
        dfs(j, tickets, visited, 1, answer)
        if len(answer) == len(tickets) + 1:
            break
        else:
            answer.clear()

    return answer


def dfs(start, tickets, visited, depth, answer):
    if depth == len(tickets):
        answer.append(start[0])
        answer.append(start[1])
        return

    place = list()
    i = 0
    for ticket in tickets:
        if ticket[0] == start[1]:
            if not visited[i]:
                ticket.append(i)
                place.append(ticket)
        i += 1
    place.sort(key=lambda x: x[1])

    if not place:
        if answer:
            answer.pop()
            visited[start[2]] = False

    for i in place:
        if not visited[i[2]]:
            visited[i[2]] = True
            answer.append(start[0])
            dfs(i, tickets, visited, depth + 1, answer)