defaultdict 함수와 사용 방법

이카루스·2024년 1월 16일

코드공부

목록 보기

4/8

일반적인 딕셔너리 값 처리

def count_letters(word):
    counter = {}
    for letter in word:
        if letter not in counter:
            counter[letter] = 0
        counter[letter] += 1
    return counter

collections.defaultdict

defaultdict 클래스의 생성자로 기본값을 생성해주는 함수를 넘기면, 모든 키에 대해서 값이 없는 경우 자동으로 생성자의 인자로 넘어온 함수를 호출하여 그 결과값으로 설정한다.

from collections import defaultdict

counter = defaultdict(int)
for item in my_list:
    counter[item] += 1
    
print(counter)

두 함수 모두 동일한 최종 결과를 달성하지만 collections.defaultdict를 사용하면 두 번째 함수가 다양한 계산 작업에 더 효율적이고 읽기 쉽고 적응 가능해집니다.

BFS최단경로

BFS 개요

시작점: BFS는 루트 노드에서 시작하여 다음 깊이 수준의 노드로 이동하기 전에 현재 깊이의 모든 이웃을 탐색합니다.
큐 데이터 구조: BFS는 큐를 사용하여 방문할 노드를 추적합니다. 대기열을 사용하면 노드가 검색된 순서대로 처리됩니다.

BFS 알고리즘의 단계

초기화:
루트 노드(또는 그래프의 경우 시작 노드)를 대기열에 넣는 것으로 시작합니다.
주기와 반복을 피하기 위해 방문한 노드를 추적하는 세트 또는 목록을 만듭니다.

탐험:
대기열이 비어 있지 않은 동안 다음 단계를 반복하십시오.

큐의 앞부분에서 다음 노드를 큐에서 제거(제거)합니다.
해당 노드가 목표인지 확인합니다(찾고 있는 특정 대상이 있는 경우). 그렇다면 검색이 종료될 수 있습니다.
목표가 아니거나 구체적인 목표가 없다면 노드를 처리합니다(노드의 값을 출력하거나 계산을 수행하는 등).
노드를 방문한 것으로 표시합니다.

이웃 방문:
노드의 각 이웃에 대해 아직 방문하지 않은 경우 대기열에 추가하고 방문한 것으로 표시합니다.
이렇게 하면 그래프나 트리의 다음 레벨로 이동하기 전에 모든 이웃을 탐색할 수 있습니다.

완료:
알고리즘은 대기열이 빌 때까지 계속됩니다.
트리에서는 모든 노드를 방문했음을 의미합니다. 그래프에서는 특정 대상이 발견되었거나 더 이상 탐색할 연결된 구성 요소가 없음을 의미할 수 있습니다.

BFS의 특징

최단 경로: 비가중 그래프에서 BFS는 시작 노드에서 도달 가능한 다른 노드까지의 최단 경로를 보장합니다.
비재귀적: 깊이 우선 검색(DFS)과 달리 BFS는 일반적으로 대기열의 도움을 받아 비재귀적으로 구현됩니다.
레벨 순서 탐색: 트리에서 BFS는 다음 레벨로 이동하기 전에 트리의 각 레벨을 완전히 방문하는 레벨 순서 탐색에 해당합니다.

사용 사례

비가중 그래프에서 최단 경로 찾기.
트리의 레벨 순서 순회.
그래프가 연결되어 있는지, 그래프에 순환이 포함되어 있는지 확인합니다.
하나의 연결된 구성 요소 내에서 모든 노드를 찾습니다.

Example

루트에서 시작하는 트리를 상상해 보세요. BFS는 먼저 루트의 모든 자식을 탐색한 다음 해당 자식의 모든 자식 등을 탐색합니다. 그래프에서는 초기 노드에서 시작하여 바로 이웃을 탐색한 다음 각 이웃을 탐색하고 이 방식을 계속하여 점진적으로 점점 더 멀리 있는 노드를 탐색합니다.

결론

BFS는 깊이 제약 없이 최단 경로 또는 포괄적인 탐색이 필요한 시나리오에서 단순성과 광범위한 적용 가능성으로 알려진 컴퓨터 과학의 필수 알고리즘입니다. 솔루션이 깊지 않거나 모든 노드를 방문해야 하는 문제에서 특히 선호됩니다.

defaultdict로 BSF 알고리즘 구현하기

노드 간 최단 경로를 찾는 기능을 포함하도록 DirectedGraph 클래스를 향상시키기 위해 BFS(Breadth-First Search) 알고리즘을 구현할 수 있습니다. BFS는 우리와 같은 비가중 그래프에서 최단 경로를 찾는 일반적인 접근 방식입니다.

다음은 두 노드 사이의 최단 경로를 찾기 위해 find_shortest_path 메서드가 추가된 수정된 DirectedGraph 클래스입니다.

from collections import defaultdict, deque

class DirectedGraph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def display_graph(self):
        for node in self.graph:
            for neighbour in self.graph[node]:
                print(f"{node} -> {neighbour}")

    def find_shortest_path(self, start, end):
        # Keep track of visited nodes and paths
        visited = set()
        queue = deque([(start, [start])])  # Queue of tuples (node, path to node)

        while queue:
            current, path = queue.popleft()
            if current == end:
                return path  # Return the first path found to the end node

            if current not in visited:
                visited.add(current)
                for neighbour in self.graph[current]:
                    if neighbour not in visited:
                        queue.append((neighbour, path + [neighbour]))

        return None  # No path found

# Example Usage       
graph = DirectedGraph()
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
graph.add_edge(4, 1)

graph.display_graph()

# Find shortest path
print("Shortest path from 1 to 4:", graph.find_shortest_path(1, 4))

이 코드에서는:

find_shortest_path 메소드는 BFS를 사용하여 start 노드에서 end 노드까지의 최단 경로를 찾습니다.
방문한 노드와 각 노드에 도달하기 위해 이동한 경로를 추적합니다.
start 노드에서 end 노드까지 찾은 첫 번째 경로를 반환합니다. 경로를 찾을 수 없으면 None을 반환합니다.
이 BFS 접근 방식은 비가중 그래프에서 두 노드 사이의 간선 수 측면에서 최단 경로를 찾는 데 적합합니다. 가중치 그래프 또는 더 복잡한 시나리오의 경우 Dijkstra 또는 A*와 같은 다른 알고리즘이 더 적합할 수 있습니다.