ProgrammersLv3여행경로

문제

풀이

• 가장먼저 시작 티켓을 담아두고, 방문여부를 판단하는 T/F 배열, 여행 경로를 저장하는 Trip 배열을만든다.
• DFS로 탐색한다. 조건은 도착지와 시작지가 같은 곳을 찾는다
• 결과들을 알파벳 순으로 비교하여 answer 에 저장한다.

코드

answer = []
def dfs(visited, tickets, start_ticket, trip):
    global answer
    if len(trip) == len(tickets):
        new_answer = []
        for i in range(len(trip)):
            new_answer.append(trip[i][0])
        new_answer.append(trip[-1][1])
        
        if len(answer) == 0:
            answer = new_answer
        else:     
            for i in range(len(answer)): 
                if new_answer[i] == answer[i] : continue
                elif new_answer[i] < answer[i]: answer = new_answer
                else: break

    for i in range(len(tickets)):
        if tickets[i][0] == start_ticket[1] and not(visited[i]):
            visited[i] = True
            trip.append(tickets[i])
            dfs(visited, tickets, tickets[i], trip)
            visited[i] = False
            trip.pop()
def solution(tickets):
    # 중복으로 담기는 경우도 있으니 visited 에 비행기표를 담는게 아니라 T/F 로 넣어 두자!
    start_ticket = []
    visited = [False] * len(tickets)
    tickets.sort()

    for i in range(len(tickets)):
        trip = []
        if tickets[i][0] == "ICN":
            start_ticket = tickets[i]
            visited[i] = True
            trip.append(start_ticket)
            dfs(visited, tickets, start_ticket, trip)
            visited[i] = False
            trip.pop()
    print("answer",answer)

    return answer

느낀점

• 항상 느끼지만, 삽질은 마음이 아프다.
• 알파벳 순서를 비교할 때 S 와 I 중에 나는 S 가 앞인줄알고 1시간을 허비했다.
• 중복된 티켓이 있는 줄 몰랐다. 테스트 케이스 힌트 보고 알았다. 그리고나서 visited 배열에 원소를 배열로 담는 것이 아니라 T/F 로 담을 수 있게 되었다.