[프로그래머스] 여행경로

문제 링크

[프로그래머스] 여행경로 Link

생각의 흐름

1. 조건에 맞는 경우의 수를 구해야 함을 파악
2. DFS, BFS 중에 선택
3. 코드로 구현

<문제 파악>

하나의 방향그래프를 순회한다고 생각하면 편하다. 시작점을 "ICN"으로 방향그래프를 탐색하면서 배열에 저장하고 종료조건에 따라 끝까지 도달한 배열을 종합하는 배열에 추가해준다. 종합한 배열을 정렬하면 답이 나온다.

<BFS, DFS 선택하기>

(그래프의 가중치가 1이라는 가정)
BFS : 최단경로 찾기
DFS : 모든 경로를 검색하는 기법, 백트래킹 사용

시작점이 주어지고 모든 경우의 수를 찾아 종합한 후 정렬을 해야하기 때문에 DFS를 선택한다.
그리고 여러가지 루트가 존재하기 때문에 백트래킹 기법을 사용해야 한다.

<BFS 사용하여 코드로 구현하기>

<포인트>

1. 함수의 인자를 보내는 아이디어
2. 백트래킹 사용

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

후기

모든 경우의 수를 찾는 경우에 백트래킹을 사용한다는 점에서 공부할 것이 많은 문제였다. 함수의 인자를 넘겨주는 아이디어가 쉽지 않았다. 함수 안에 함수를 넣는 것이 꽤 편리했고, 이제는 visit 함수도 Bool 형식 리스트로 True False를 사용하려 한다.