[Programmers] 여행경로 (DFS/BFS Lv.3) - Python

꼬마요리사레미·2023년 5월 28일

Algorithm

목록 보기

23/41

1. 문제

2. 풀이

코드

from collections import defaultdict

def solution(tickets):
    answer = []
    routes = defaultdict(list)
    
    for start, end in tickets:
        routes[start].append(end)
    for route in routes:
        routes[route].sort()
    
    stack =['ICN']
    while stack:
        current = stack[-1]
        if routes[current]:
            next_dest = routes[current].pop(0)
            stack.append(next_dest)
        else:
            answer.append(stack.pop())
    answer.reverse()

입력 및 출력

tickets = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]

>> ["ICN", "JFK", "HND", "IAD"]

3. 로직

defaultdict를 사용하여 routes라는 딕셔너리를 생성한다. 이 딕셔너리는 각 도시를 키(key)로 가지며, 해당 도시에서 출발하는 항공권의 목적지(destination)들을 값(value)으로 가진다.
주어진 항공권 정보를 순회하면서 routes 딕셔너리에 출발지를 키로 하여 목적지를 추가한다.
routes 딕셔너리의 각 키(start)에 대한 값(end)을 정렬한다다. 이는 알파벳 순서로 방문해야 하기 때문이다.
스택(stack)을 생성하고 ICN(시작 도시)을 스택에 추가한다.
스택이 비어있지 않은 동안 다음을 반복한다:

스택의 맨 위에 있는 도시를 current로 설정한다.
만약 routes[current]가 비어있지 않다면, routes[current]에서 가장 앞에 있는 도시를 꺼내어(next_dest) 스택에 추가한다. 이는 현재 도시에서 다음 도시로 이동하는 것을 의미한다.
routes[current]가 비어있다면, 현재 도시에서 더 이상 갈 수 있는 도시가 없으므로 answer에 current를 추가하고 스택에서 제거한다.
answer를 역순으로 정렬한다. 이는 출발지부터 도착지까지 순서대로 방문하기 위한 조치이다.

결과적으로, answer에는 모든 도시를 한 번씩 방문하는 여행 경로가 저장됩니다.defaultdict는 collections 모듈에 속하는 클래스로, 기본값(default value)을 지정하여 딕셔너리(dictionary)를 생성하는 방법입니다. 일반적인 딕셔너리와 비슷한 기능을 제공하지만, 존재하지 않는 키(key)에 접근할 경우 미리 정의한 기본값을 반환합니다.

defaultdict를 사용하기 위해서는 from collections import defaultdict와 같이 모듈을 임포트해야 합니다.

defaultdict는 기본값을 설정하기 위해 호출 가능한 객체(callable object)를 인자로 받습니다. 대부분의 경우 기본값으로 int, list, set과 같은 내장 자료형을 사용합니다. 기본값으로 사용될 내장 자료형을 지정하면, 딕셔너리의 키에 해당하는 값이 존재하지 않을 때 해당 자료형의 기본값이 자동으로 생성됩니다.

예를 들어, 다음과 같이 defaultdict를 사용하여 딕셔너리를 생성할 수 있습니다:

4. 사용된 함수

defaultdict

defaultdict는 collections 모듈에 속하는 클래스로, 기본값(default value)을 지정하여 딕셔너리(dictionary)를 생성하는 방법이다. 일반적인 딕셔너리와 비슷한 기능을 제공하지만, 존재하지 않는 키(key)에 접근할 경우 미리 정의한 기본값을 반환한다.

defaultdict를 사용하기 위해서는 from collections import_ defaultdict와 같이 모듈을 임포트해야 한다.

defaultdict는 기본값을 설정하기 위해 호출 가능한 객체(callable object)를 인자로 받는다. 대부분의 경우 기본값으로 int, list, set과 같은 내장 자료형을 사용한다. 기본값으로 사용될 내장 자료형을 지정하면, 딕셔너리의 키에 해당하는 값이 존재하지 않을 때 해당 자료형의 기본값이 자동으로 생성된다.

예를 들어, 다음과 같이 defaultdict를 사용하여 딕셔너리를 생성할 수 있다.

from collections import defaultdict

my_dict = defaultdict(list)

defaultdict(list)의 초기 형태는 모든 키(key)에 대해 빈 리스트([])를 가지는 defaultdict이다. defaultdict(list)를 사용하여 딕셔너리를 생성하면, 모든 키에 대해 초기값으로 빈 리스트가 할당된다. 이후에는 리스트를 추가하거나 조작하는 작업을 수행할 수 있다.

이후에는 딕셔너리의 키에 해당하는 리스트에 요소를 추가하거나 조작할 수 있다.

my_dict["key"].append(1)
my_dict["key"].append(2)
my_dict["key"].append(3)

print(my_dict["key"])  # 출력: [1, 2, 3]

위 코드에서 my_dict["key"]는 defaultdict의 특성으로 인해 초기값인 빈 리스트가 자동으로 생성되고, append() 메서드를 사용하여 요소를 추가할 수 있다. 결과적으로 my_dict["key"]는 [1, 2, 3]이 된다.