[프로그래머스] 여행경로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 모든 경로를 탐색하는 문제이므로 dfs 알고리즘을 활용해 해결해보고자 하였다.

한 경로에서 티켓은 모두 사용해야 하며, 티켓은 한 번씩만 사용할 수 있으므로 이를 저장하기 위한 방문 리스트를 생성한다.

만약 경로를 저장하는 리스트의 원소 개수가 티켓의 개수 + 1개이면(시작 ICN 포함) 모든 티켓을 한 번씩만 사용한 경로이므로 정답 리스트에 해당 경로를 추가한다.

그게 아니라면 티켓을 인덱스를 붙여 하나씩 불러오고 현재 위치에서 출발하는 티켓 중 아직 사용하지 않은 티켓이면 해당 티켓을 사용한 티켓으로 표시하고 dfs 알고리즘을 재귀적으로 사용한다.

해당 경로의 dfs 탐색을 모두 마치면 다른 경로가 있을 수도 있으므로 방금 사용한 티켓을 사용하지 않은 티켓으로 다시 표시한다.

최종적으로 저장된 정답 리스트의 원소들을 알파벳 순서로 정렬한 뒤, 가장 앞의 원소를 정답으로 반환한다.

 

1. 티켓을 한 번씩만 사용하기 위해 티켓 사용을 저장할 리스트를 생성한다. visited = [False] * len(tickets)
2. dfs 알고리즘을 함수로 구현한다. 매개변수로 현재 출발 위치와 현재까지 이동한 경로를 준다. def dfs(start, path)
   1. 만약 현재까지 이동한 경로가 모든 티켓을 사용한 경로라면 if (len(path) == len(tickets) + 1)
      1. 정답 리스트에 해당 경로의 경우를 추가한다. answer.append(path)
      2. 정답을 찾았으므로 아래 코드를 수행하지 않고 반환한다. return
   2. 반면, 아직 더 이동해야 한다면 티켓을 하나씩 불러오며 for idx, ticket in enumerate(tickets)
      1. 만약 해당 티켓의 출발지가 현재 위치이고, 아직 사용하지 않는 티켓이라면 if (ticket[0] == start) and (not visited[idx])
         1. 해당 티켓을 사용한다. visited[idx] = True
         2. 사용하는 티켓의 도착지를 다음 출발지로 하고, 현재까지의 경로에 사용하는 티켓의 도착지를 추가하여 dfs 함수를 다시 호출한다. dfs(ticket[1], path + [ticket[1]])
         3. 가능한 경로가 여러 개일 수 있으므로 재귀적으로 dfs 함수를 끝까지 수행한 후, 다른 경로 탐색을 위해 방금 사용한 티켓을 사용하지 않은 것으로 다시 저장한다. visited[idx] = False
3. 처음 출발지는 무조건 ICN이고, 이에 따라 경로에 ICN을 추가하여 dfs 함수를 수행한다. dfs("ICN", ["ICN"])
4. 최종적으로 도출된 정답 리스트의 값들을 알파벳 순서로 정렬한다. (가능한 경로가 여러 개일 경우, 알파벳 순서가 앞서는 경로를 반환) answer.sort()
5. 정렬한 뒤 제일 앞에 있는 정답을 반환한다. return answer[0]

3. 소스코드

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

    answer.sort()
    
    return answer[0]

추가로 제가 문제를 풀어보면서 활용한 테스트 케이스입니다.

print(solution([["ICN", "BBB"], ["BBB", "ICN"], ["ICN", "AAA"]]))
# ["ICN", "BBB", "ICN", "AAA"]
print(solution([["ICN", "AAA"], ["AAA", "ICN"], ["ICN", "CCC"], ["CCC", "ICN"], ["ICN", "DDD"], ["DDD", "AAA"]]))
# ["ICN", "AAA", "ICN", "CCC", "ICN", "DDD", "AAA"]
print(solution([["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]]))
# ["ICN", "CCC", "DDD", "ICN", "AAA", "BBB", "AAA", "BBB"]