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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

코드를 작성하기 위한 순서는 다음과 같다.

1. tickets의 첫번째 원소가 "ICN"인 경우, stack에 넣어주고 dfs 함수를 호출한다.

2. dfs 함수에서 stack의 길이와 tickets의 길이+1이 같은 경우, 모든 여행 경로가 완성된 것이므로 answer에 stack을 넣어준다.

3. 해당 도시를 방문하지 않았고 첫번째 원소와 stack의 마지막 원소가 같으면 여행 경로에 해당되므로, stack에 넣어주고 dfs 함수를 재귀호출한다.

4. 여러 경로가 있다면 알파벳 순으로 낮은 값을 반환해야하기에 return min(answer)을 해준다.

def solution(tickets):
    answer = []
    
    def dfs():
        if len(stack) == len(tickets)+1: #2번
            answer.append(stack[:]) #재귀 호출에서 stack은 같은 주소값을 사용하기 때문에 answer.append(stack)을 해주면 얕은 복사가 일어나서 엉뚱한 값이 append된다. 따라서 이와 같은 형태를 사용해야한다.
        for j in range(len(tickets)):
            if not visited[j] and stack[-1] == tickets[j][0]: #3번
                visited[j] = True
                stack.append(tickets[j][1])
                dfs() #다시 dfs 함수를 호출한다.
                visited[j] = False #재귀 호출 후, 다른 경우의 수를 만들어주기 위해서 방문 여부를 false로 바꾸고 stack.pop()을 해준다.
                stack.pop()
    
    for i in range(len(tickets)):
        stack = []
        visited = [False for _ in range(len(tickets))]
        if tickets[i][0] == "ICN": #1번
            stack.append(tickets[i][0])
            stack.append(tickets[i][1])
            visited[i] = True
            dfs()
        
    return min(answer) #4번

사실 다른 분의 풀이를 조금 참고하였다.

그중에서 공부할만한 부분이 있었는데, 바로 answer.append(stack[:])이다.

코드에 주석으로 설명이 달려있어서 설명은 따로 하지 않겠지만, 이를 통하여 파이썬에는 얕은 복사와 깊은 복사가 있다는 것을 알게되었다.

그 밖에서 deepcopy 모듈은 이름 그대로 갚은 복사에 사용되는 점도 새로 알게되었다.

또한 초기에 코드를 작성할 때는 알파벳 순으로 tickets을 정렬하여 경우의 수가 여러 개면 answer[0]을 반환하여 사전상 가장 빠른 경우를 반환하게 하였다.

하지만, 위의 코드와 같이 문자열도 min을 사용할 수 있는 점을 기억하면 꽤나 유용하게 사용할 수 있을 것 같다.

그리고 dfs 함수를 재귀 호출한 후에 방문 여부를 False로 바꿔주고 stack.pop()을 하는 것을 빼먹어 틀렸었는데, dfs를 사용할 때 꼭 기억해야겠다.