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

프로그래머스

---

나의 풀이

• 가능한 여러 경로를 얻고, 이 중에서 가장 앞서는 경로를 찾는 것이 핵심이다.
• 이중에서 가장 앞서는 경로를 처리하는데 어려움을 느껴 다른 사람의 풀이를 참고했다.

백트래킹 활용

• 현재 위치 정보를 전달해서 중복된 방문을 제한했다.
• [ic]path[/ic] 들을 저장해둔 [ic]answer[/ic]를 정렬하면서 가장 앞서는 경로를 얻을 수 있었다. 

from collections import defaultdict

def solution(tickets):
    # 방문 여부
    visited = defaultdict(list)
    # 그래프
    graph = defaultdict(list)
    start = "ICN"
    goal = len(tickets) + 1
    # 경로 정보
    answer = []
    # 그래프 정보 저장
    for ticket in tickets:
        a, b = ticket
        graph[a].append(b)
        visited[a].append(False)
    
    def dfs(now, path):
        nonlocal goal

        if len(path) == goal:
            answer.append(path)
            return  
        # 순차적으로 탐색
        for j in range(len(graph[now])):
            if not visited[now][j]:
                # 아직 방문하지 않은 경우
                nxt = graph[now][j]
                visited[now][j] = True
                dfs(nxt, path + [nxt])
                visited[now][j] = False
    # 시작은 무조건 ICN
    dfs("ICN", ["ICN"])
    answer.sort()
    return answer[0]

정렬 활용

• 가능한 모든 경로를 저장하는 대신, 미리 방문할 경로를 정렬해둬 한번에 정답 경로를 구할 수 있다.
• 알파벳이 앞서는 도시를 먼저 방문하고, 더이상 이동이 불가능하면 [ic]path[/ic]에 입력하는 방식이다.
  • 따라서 [ic]path[/ic]를 역순으로 반환하면 정답 경로를 얻을 수 있다.

from collections import deque, defaultdict

def dfs(graph):
    # 시작점 입력
    stack = deque()
    stack.append("ICN")   
    path = []
    while stack:
        # 출발 도시
        start = stack.pop()
        # 더이상 출발 - 도착 불가능할 경우 path에 저장
        if start not in graph or not graph[start]:
            path.append(start)
        # 방문 가능할 경우
        else:
            stack.append(start)
            stack.append(graph[start].pop())
    return path[::-1]
            
def solution(tickets):
    # 그래프 생성
    graph = defaultdict(list)
    for a, b in tickets:
        graph[a].append(b)
    # 도착 리스크 역순 정렬
    # DFS에서 먼저 선택될 수 있도록
    for k in graph.keys():
        graph[k].sort(reverse = True)
    answer = dfs(graph)
    return answer

참고

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

여행 경로 - 파이썬(Python)