여행경로

날짜 : 2023. 09. 29

사용 언어 : python

 

문제

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

 

 

코드

def solution(tickets):
    used = [False] * len(tickets)  # 사용여부
    res = list()
    def dfs(now, path):
        # print(now, path)
        if len(path) == len(tickets) + 1:
            res.append(path)
            return
        for i in range(len(tickets)):
            if not used[i] and tickets[i][0] == now:  # 현재 체크하는 티켓 사용 x, 출발지가 동일
                used[i] = True  # 사용체크
                dfs(tickets[i][1], path + [tickets[i][1]]) # 리스트간 더하기
                used[i] = False
    dfs("ICN", ["ICN"])
    res.sort()
    return res[0]

 

 

풀이

- 모든 티켓에 대해서 여정을 만든 후, 전부 사용했을 때 해당 여정을 하나의 리스트에 전부 넣은 다음 리턴하는 방식의 백트래킹을 진행한다.

- 시작은 무조건 "ICN"이고, 여정또한 맨 앞에 "ICN"을 넣어 시작한다.

- 그 다음 모든 티켓에 대해 탐색하고, 지정된 티켓의 출발지와 현재 기준지와 비교했을 때 동일하고, 해당 티켓을 사용하지 않은 경우 해당 티켓을 사용처리한 다음, 목적지로 이동하는 방식으로 재귀한다.

- 그 다음 재귀에서 빠져나왔을 때 사용여부를 다시 미사용으로 처리한다.

- 이렇게 백트래킹을 진행한 후, 모든 여정에 대해 오름차순으로 정렬한 다음 맨 처음의 여정을 리턴한다.

 

 

알게된 점

- 일반적으로 2차원 배열로 이루어진 DFS만 풀다가 이런 방식의 (시작점, 도착점) 형태의 그래프를 받으니 굉장히 낯설게 느껴졌다.

- 이 문제에서 가장 고민했던 부분은 명실상부 방문처리를 어떻게 해야할까였다.

- 도시 개수대로 2차원 배열을 만들어서 돌린다면 1만 * 1만의 케이스가 발생할 것이기 때문에 분명 시간초과가 걸릴 것이어서 해당 케이스는 배제했고, 그것 이외에 다른 아이디어는 떠오르지 않았다.

- 여정(path)을 저장해서 정렬 후 리턴하는 아이디어는 떠올리지 못해서 다른 사람의 풀이를 참고했고, 해당 아이디어를 확인하여 문제를 해결할 수 있었다.

- 추가로 리스트의 덧셈의 개념도 학습할 수 있었다.

ex) a = [1, 2, 3, 4] / b = [5, 6, 7] -> c = a + b -> [1, 2, 3, 4, 5, 6, 7]

그치만 [1, 2] + [1, [3, 4]]의 형식인 경우 오류가 발생한다.

 

 

참고 사이트

- https://lottegiantsv3.tistory.com/27

여행 경로 - 파이썬(Python)