[Algorithm] 프로그래머스 43164 : 여행경로 - dfs

문제
https://school.programmers.co.kr/learn/courses/30/lessons/43164
풀이
https://github.com/nowChae/algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/3/43164.%E2%80%85%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C/%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C.py

ICN부터 시작해 모든 티켓을 사용하여 여행경로를 짜는 문제였다. 여러 개의 경로가 나올 경우에는 알파벳 순서가 가장 앞서는 경로를 return하는 조건이 있어서 무조건 알파벳 앞 순서를 방문하도록 구현해보았다. 이렇게 구현했을 경우에 기본 테스트는 성공하였지만, 제출하였을 때 테스트 1,2번에서 실패했다. 그 이유는 무조건 알파벳 앞 순서인 경로를 선택하면 주어진 항공권을 다 사용하지 못하고 경로가 끊길 수 있는 경우가 발생하기 때문이었다. 따라서 이런 상황에서는 해당 순서에서 다른 공항을 선택하도록 구현해줘야 했다.

이 부분을 구현하는 데에 있어서 이해는 했지만 실제로 구현이 어려워 구글링을 통해 문제를 해결했다. 해결 코드를 작성하는 데에 answer.append() 부분에서 처음에는 그냥 path를 바로 추가하도록 하였는데, path를 그대로 사용하게 되면 재귀를 사용하는 이 코드에서는 다른 부분에 의해 path 값이 영향을 받아 실패를 띄웠다. 따라서 path 값을 그대로 넣는 것이 아니라 [:] 을 통해 복사된 값을 넣도록 만들었다.

dfs를 사용하여 이 문제를 풀어보았는데 다음 번엔 bfs를 사용하여 풀어보려고 하며, dfs로도 다시 한 번 풀어봐야겠다.

< 풀이 코드 - 테스트 1,2 실패 >

# test 1, 2 실패 
# 무조건 알파벳 앞순서를 방문하게 해서 
# 모든 항공권을 이용하지 못하고 종료됨

def dfs(start, tickets, visited, answer):
    answer.append(start)
    destination = []
    for i in range(len(tickets)):
        if (not visited[i]) and (tickets[i][0] == start):
            destination.append([tickets[i][1],i])
    if not destination: 
        return
    if len(destination) > 0:
        destination = sorted(destination)
    visited[destination[0][1]] = True
    dfs(destination[0][0], tickets, visited,answer)


def solution(tickets):
    visited = [False]*len(tickets)
    answer = []
    dfs("ICN", tickets, visited, answer)
    return answer

< 풀이 코드 >

def dfs(start, visited, tickets, path, answer):
    if len(path) == len(tickets)+1 :
        answer.append(path)
        return 
    for i in range(len(tickets)):
        if (not visited[i]) and tickets[i][0] == start:
            visited[i] = True
            dfs(tickets[i][1], visited, tickets, path+[tickets[i][1]], answer)
            visited[i] = False
    
    
    
def solution(tickets):
    visited = [False] * len(tickets)
    answer = []
    path = []
    dfs("ICN", visited, tickets, ["ICN"], answer)
    
    answer.sort()
    return answer[0]