[PROGRAMMERS] 깊이/너비 우선 탐색 : 여행경로 Python

이번 문제는 문제 카테고리가 깊이/너비 우선 탐색이기 때문에 문제를 풀 때 어느 정도 힌트를 얻을 수 있었다.

이 문제는 항공권 정보가 담긴 (출발지 , 목적지) 티켓들이 적혀있다. 이 티켓들로 모든 도시들을 방문하고자 할 때 경로를 반환해야 한다. 추가 제약사항으로는 모든 도시를 방문하는 경우의 수가 두 개 이상 있을 때, 알파벳순으로 가장 앞의 값을 리턴해야 한다는 점이 있다.

내가 이문제를 풀면서 생각한 두 가지 키포인트는
1. 주어진 항공권은 모두 사용해야 한다 + 이 문제는 시간 제약이 없다
2. 경로를 return 해야 한다.
이다

첫 번째로 주어진 항공권을 모두 사용해야 한다는 점에서 나는 시간단축을위해 해쉬자료형이나, 방문기록을 위해 인접행렬을 만들 필요없이 항공권의 인덱스와 갯수로 방문체크를 할 수 있을것이라고 생각했다.

그리고 경로를 정답으로 해야한다는 점에서 경로 체크가 힘든 BFS보다는 DFS로 문제를 푸는 것이 적합하다고 생각했다.

이를 코드로 나타낸다면,

def solution(tickets):
    # 모든 도시를 방문하는 방법을 찾는 함수
    def dfs(now):
        nonlocal answer
        # 종료조건 : 모든 티켓을 사용확인
        if sum(v) == N:
            # 알파벳 순서 확인
            if ''.join(answer) >= ''.join(route):
                answer = route[:]
            return

        # 티켓 확인
        for t_idx in range(N):
            if tickets[t_idx][0] == now and not v[t_idx]:
                v[t_idx] = 1
                route.append(tickets[t_idx][1])
                dfs(tickets[t_idx][1])
                route.pop()
                v[t_idx] = 0

    # 1.변수생성 
    N = len(tickets)
    v = [0] * N
    route = ["ICN"]
    answer = ["ZZZ"]
    # 2. DFS로 정답찾기
    dfs("ICN")
    return answer

이렇게 된다.

방문 체크를 티켓의 사용 여부로 하니, 종료 조건 역시 모든 티켓을 방문했는지 여부로 확인할 수 있었고, 이를 이용해 DFS(완전 탐색)을 활용하면 쉽게 답을 구할 수 있었다.

조금 헷갈렸던 점은 모든 도시를 순회할 수 있는 방법이 여러 개일 때 알파벳상 가장 앞에 있는 수를 리턴으로 반환하는 점이었다. 이 부분에서 '>='을 이용하여 문자열에 크기 비교를 했다. 문자열 크기 비교는 항상 헷갈렸었는데, 같이 스터디하시는 분이 알려주신 '사전 찾기'를 생각하게 된 이후로 헷갈리지 않게 됐다.

말 그대로 문자열 비교는 사전에서 그 문자를 찾을 때 앞에 있는 문자가 비교식을 했을 때 더 큰 숫자라는 것이다. 그렇기 때문에 answer변수에 임시로 넣은 'ZZZ'는 다른 문자열들과 비교했을 때 가장 작은 수가 될 수 있었다.

문자열의 크기 비교에 헷갈렸다면 또 엄청 헤매었을뻔한 문제이지만 다행히 잘 마무리할 수 있었다.

오늘도 하루한개 알고리즘 파이팅!