LV 3: 여행경로

문제 링크

LV 3: 여행경로

구현 방식

• dfs(백트래킹)을 이용해서 풀어주었다
• visit 처리가 좀 중요했는데, visit을 tickets 크기의 1차원 배열로 선언해주고 매번 tickets를 순회해주면서 조건에 만족하는 경우 재귀 호출 해주었다

코드

from collections import deque

def solution(tickets):
    tickets.sort()
    visit = [False]*len(tickets)

    def dfs(src, path):
        if len(path) == len(tickets)+1:
            answer.append(path)
            return

        for i in range(len(tickets)):
            if src == tickets[i][0] and not visit[i]:
                visit[i] = True
                dfs(tickets[i][1], path+[tickets[i][1]])
                visit[i] = False #백트래킹

    answer = []
    dfs('ICN', ['ICN'])
    return answer[0]