[Programmers, Python] Lv3. 여행 경로

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

프로그래머스 - Lv3. 여행 준비

DFS 알고리즘의 이해 부족을 느낀 문제이다.

일단 문제를 처음 봤을 때 '그래프 탐색 문제, 항공권 정보는 딕셔너리로 정리하는게 좋겠다.'라고 생각했다. 여기까지는 좋았는데, 이후 익숙한 BFS로 문제를 풀려고 했지만 도저히 풀이 방법이 생각나지 않았다. 결국 다른 분들의 코드를 참고했다.

이 문제는 DFS, BFS 두 방법 모두 풀이가 가능한데 문제 요구사항에 더 적합한 DFS 풀이 방법 먼저 살펴보자.

DFS 스택 문제 풀이 코드

defaultdict
defaultdict는 딕셔너리를 만드는 dict 클래스의 서브 클래스이다.
작동 방식은 유사한데, defaultdict의 인자로 주어지는 객체의 기본값을 딕셔너리값의 초기값으로 지정할 수 있다.

from collections import defaultdict
def solution(tickets):
    dict = defaultdict(list)

    for s,e in tickets:
        dict[s].append(e)

    for key in dict.keys():
        dict[key].sort(reverse=True)

    answer = []
    path = ["ICN"]

    while path:
        now = path[-1] # 현재 경로

        if now not in dict or len(dict[now])==0: # 다음 경로가 없다 -> 모든 공항을 방문했다. 역순으로 answer에 추가
            answer.append(path.pop())
        else:
            path.append(dict[now].pop())
    return answer[::-1]

코드의 논리 흐름은 매우 간단하다. 딕셔너리 구조로 항공기 경로를 저장하고, value 값을 내림차순으로 정리한다. 첫 출발지는 "ICN"으로 고정이기 때문에 path에 "ICN"을 넣어두고 while 문을 시작한다. 이때 현재 경로가 딕셔너리의 key 값으로 없거나, 현재 경로(key)에 대한 value의 개수가 0개라면 모든 공항을 방문했다는 것이기 때문에 경로가 저장되어 있는 path에서 pop()으로 꺼내 최종 반환값이 될 answer 에 추가한다.

pop으로 빼서 answer에 추가했기 때문에 결과를 리턴할 때는 값의 순서를 뒤집어준다.

BFS 문제 풀이 코드

from collections import deque

def solution(tickets):
    answer = []
    tickets.sort(key = lambda x: (x[0], x[1]))

    # 현재까지의 경로와, 남은 티켓을 큐에 튜플로 저장
    dq = deque([(["ICN"], tickets)])

    while dq:
        now_path, now_t = dq.popleft()

        # 남은 티켓이 없다면, 그 때의 path가 알파벳 순서 상 가장 앞선 완성된 경로
        if len(now_t) == 0:
            answer = now_path
            break

        valid_idx = -1
        for i in range(len(now_t)):
            if now_t[i][0] == now_path[-1]:
                valid_idx = i
                break

        # 남은 티켓이 있는 상태에서 다른 공항으로 가는 티켓도 없으므로 현재 루트는
        # 유효하지 않은 루트이므로 continue
        if valid_idx == -1:
            continue

        # 출발지가 현재 위치한 공항인 티켓을 차례로 순회하며 정보를 큐에 넣어줌
        while valid_idx < len(now_t) and now_t[valid_idx][0] == now_path[-1]:
            dq.append((now_path + [now_t[valid_idx][1]], now_t[:valid_idx] + now_t[valid_idx+1:]))

            valid_idx += 1

    return answer