[프로그래머스] 파이썬 _ 여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

 

문제유형 : DFS

 

문제풀이 :

• 하나의 여행지를 노드로 보지않고 하나의 PATH(출발지~도착지)를 하나의 노드로 보고 풀었다.
• 전형적인 DFS문제이면서 살짝의 변형이 있는 문제이다.
  • ICN ~ @@@ 인 노드를 시작노드로 하여 DFS를 진행한다.
  • DFS의 depth가 tickets길이-1 이면 전체 항공권을 모두 사용한것이 되므로 지금까지의 경로를 저장하고 있던 temp값을 answer배열에 저장한다.  ( 여기서 그냥 temp를 바로 answer에 append하면 안되고 temp.copy를 이용해 값만 넣어줘야함)
  • 최종적으로 answer배열엔 모든항공권을 사용하는 가능한모든 경로가 저장되게되는데, 알파벳순으로 sort하고 첫번째값을 답으로 리턴한다.
• 사실 내코드는 알파벳순으로 1등인 한 경로만 구하는게 아니고 가능한 모든걸 다 구하고나서, sort하는 형태라서 그렇게 좋은코드같진 않다. ( test case1번에서 시간이 오래걸리게나왔다)

 

정답코드

answer = []

def solution(tickets):

    for idx , i in enumerate(tickets):
        if i[0] == "ICN":
            temp = []
            visited = [False for _ in range(len(tickets))]
            dfs(idx, i, 0, tickets, temp, visited)

    return sorted(answer)[0]

def dfs(idx, path, depth, tickets, temp, visited):
    global answer
    temp.append(path[0])

    visited[idx] = True

    if(depth == len(tickets)-1):
        temp.append(path[1])
        answer.append(temp.copy()) #그냥 temp로 해서 개헤멤... temp를주면 리스트는 주소값이 넘어가니까 이후에 temp에 변경하면 answer에도 변경된 temp가 들어가게됨...!
        temp.pop()
        return

    index = []
    # path[1]에서 출발하는 경로중 방문되지 않은 path가 있으면 걔를 인자로 주는 dfs재귀호출 (방문되지않음을 체크하기위해 index필요)
    # 도착지로부터 다시 출발하는 path를 찾고, 해당 path로 재귀호출
    for num, i in enumerate(tickets):
        if i[0] == path[1]:
            index.append(num)

    for i in index:
        if visited[i] == False:
            dfs(i, tickets[i], depth + 1, tickets, temp, visited)
            visited[i] = False  # 다시 미방문으로 처리
            temp.pop()