[프로그래머스] 여행경로 (DFS)

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

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

다른 코테스터디원이 푼 방식이 매우 인상깊어 기록으로 남긴다.

dfs 백트래킹을 이용하여 문제를 풀었다. 코드는 다음과 같다.

from collections import defaultdict
def dfs(N, graph, path, used_tickets):
    if len(used_tickets) == N:
        return path
    cur = path[-1]
    for next_city, idx in graph[cur]:
        if idx in used_tickets:
            continue
        used_tickets.add(idx)
        result = dfs(N, graph, path+[next_city], used_tickets)
        if result:
            return result
        used_tickets.remove(idx)
    return None

def solution(tickets):
    answer = []
    
    graph = defaultdict(list)
    for i, (_from, _to) in enumerate(tickets):
        graph[_from].append((_to, i))
    for v in graph.values():
        v.sort()
    
    # print(graph)
    path = ['ICN']
    used_tickets = set()
    answer = dfs(len(tickets), graph, path, used_tickets)        
    
    return answer

 

 

위 문제 풀이의 핵심은 잘못된 곳으로 탐색을 했을때 갔던 기억을 지우고 다른 곳으로 탐색을 시도하는 것이다.

예를들어 A => B => C 로 가면 전체 티켓을 소진하며 돌수가 없다. 

그러면 B 와 C로 가며 썼던 티켓을 다시 안쓴것으로 되돌리고 A=>D로 탐색시도하여

그다음 A=>B=>C 로 탐색하며

최종적으로 A=>D=>A=>B=>C 로 탐색하면 정답이 된다.

 

두번째 유의 사항은 지금까지의 지나온 경로를 저장하는 path 변수이다.

dfs 재귀로 호출할때 path+[next_city] 로 변수를 전달해준다. 이렇게하면 깊은복사가 일어나는데 

이렇게함으로써 새롭게 한단계 깊이 탐색할때마다 새로운 공간에 path 를 생성하며 저장한다.

그냥 path.append(next_city) 하지 않은 이유는 위와같이 해야 만약 잘못된 경로를 가더라도 그 path는 올바른 경로로 가는 path에 영향을 미치지 않기 때문이다. (각각 다른 메모리공간에 path를 저장하였으므로)

 

https://blockdmask.tistory.com/576

[python] 파이썬 얕은복사, 깊은복사 (copy, deepcopy, [:], =) 총 정리

---

유사문제

https://leetcode.com/problems/reconstruct-itinerary/

Reconstruct Itinerary - LeetCode