BFS, DFS, Topological Sort

BFS(너비 우선 탐색)는시작 정점에서 가까운 정점부터 차례대로 모든 정점을 방문하는 방식. 큐(Queue)를 사용하여 구현한다.

 

모든 노드를 레벨별로 탐색하고 최단 경로를 찾는 데 유용하다(가중치가 없는 경우). 고로최단 경로 찾기, 소셜 네트워크에서 '최단 연결 경로' 찾기 등에 유용하다.

from collections import deque

def bfs(graph, start_node):
    visited = set()  # 방문한 노드를 체크할 집합
    queue = deque([start_node])  # 탐색을 시작할 노드를 큐에 추가
    
    while queue:  # 큐가 비어있지 않는 동안
        node = queue.popleft()  # 큐에서 하나의 노드를 꺼냄
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node] - visited)  # 해당 노드의 인접 노드를 큐에 추가
    return visited

 

DFS(깊이 우선 탐색)는 시작 정점에서 한 방향으로 가능한 멀리 있는 정점을 방문하고, 더 이상 방문할 정점이 없으면 마지막에 통과한 정점으로 되돌아와 다른 방향의 정점을 탐색하는 방식이다. 스택(Stack) 또는 재귀 함수를 사용하여 구현한다.

 

경로의 가능성을 탐색할 때 유용하다. 순환 구조를 갖는 그래프에서 사용될 수 있다. 미로 찾기, 퍼즐 게임, 사이클 찾기 등을 구현할 때 유용하다.

def dfs(graph, start_node, visited=None):
    if visited is None:
        visited = set()  # 방문한 노드를 체크할 집합
    visited.add(start_node)
    
    for node in graph[start_node] - visited:  # 현재 노드의 인접 노드 중 방문하지 않은 노드에 대해 탐색
        dfs(graph, node, visited)
    return visited

 

Topological Sort(위상 정렬)은 방향 그래프에서 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다. 이 알고리즘은 주로 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에 적용된다. 위상 정렬의 결과는 유일하지 않을 수 있으며, 하나의 그래프에 여러 위상 정렬 결과가 존재할 수 있다.

 

DAG에서는 적어도 하나의 노드가 들어오는 간선이 없는(진입 차수가 0인) 노드가 존재한다. 위상 정렬은 진입 차수가 0인 노드를 찾아 순서대로 나열하고, 해당 노드와 연결된 간선을 제거한다. 간선 제거 후 새롭게 진입 차수가 0이 된 노드를 찾아 위 과정을 반복한다.

 

모든 노드의 진입 차수를 계산한다. 진입 차수가 0인 노드를 큐에 삽입한다. 큐에서 노드를 꺼내 해당 노드를 위상 정렬의 결과에 추가하고, 해당 노드에서 나가는 간선을 그래프에서 제거한다. 이 때, 간선 제거로 인해 새롭게 진입 차수가 0이 된

 

노드를 큐에 삽입한다. 큐가 빌 때까지 3번 과정을 반복한다. 그래프에 사이클이 없다면 모든 노드가 위상 정렬 결과에 포함된다.

from collections import deque

def topological_sort(graph):
    indegree = {u: 0 for u in graph}  # 모든 노드의 진입 차수를 0으로 초기화
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1  # 진입 차수 계산
    
    queue = deque([u for u in graph if indegree[u] == 0])  # 진입 차수가 0인 노드를 큐에 삽입
    
    top_order = []
    while queue:
        u = queue.popleft()
        top_order.append(u)
        for v in graph[u]:
            indegree[v] -= 1  # u에서 나가는 간선 제거
            if indegree[v] == 0:
                queue.append(v)
                
    if len(top_order) == len(graph):
        return top_order  # 모든 노드를 방문했다면 위상 정렬 성공
    else:
        return []  # 사이클이 존재한다면 위상 정렬 실패

 

위상 정렬은 의존성이 있는 여러 작업을 수행할 때 순서를 결정하는 데 유용하다. 예를 들어, 프로젝트에서 수행해야 할 작업들 사이에 선행 관계가 정의되어 있을 때, 각 작업을 시작하기 전에 반드시 완료되어야 하는 작업들의 순서를 결정할 수 있다. 또한, 컴파일러가 소스 코드 내의 의존성을 해결하기 위해 사용하기도 한다.

 

++백트래킹

 

백트래킹(Backtracking)은 해를 찾는 도중에 현재의 경로가 해가 될 가능성이 없다고 판단되면, 즉시 뒤로 돌아가(Backtrack) 다른 경로로 해를 탐색하는 기법이다. 이 방법은 주로 결정 문제(예/아니오로 답하는 문제)나 최적화 문제를 해결할 때 사용된다. 백트래킹은 브루트 포스(완전 탐색)를 기반으로 하되, 불필요한 경로를 조기에 차단함으로써 탐색의 효율을 높인다.

 

탐색 중에 해가 될 수 없는 경우를 빠르게 판단하여 탐색 범위를 줄인다. 이는 탐색 과정에서 불필요한 부분을 제거함으로써 탐색 시간을 단축시킨다.

 

가능한 모든 해를 나무 모양으로 구성한 것으로, 해를 찾기 위해 탐색한다. 노드마다 선택지를 고르면서 내려가되, 어떤 노드가 문제의 조건에 맞지 않는다면 그 노드의 부모로 돌아와 다른 선택지를 탐색한다.

 

백트래킹은 재귀적인 성질을 띤다. 해를 찾아가는 과정에서 각 단계에서 모든 가능성을 시도하다가 가능성이 없다고 판단되면, 바로 이전 상태로 돌아간다.

def backtrack(path):
    if 조건에 부합하는 해가 완성된 경우:
        해를 출력하거나 기록
        return
    
    for 선택 in 모든 가능한 선택지:
        if 선택이 유효한 경우:
            path에 선택을 추가
            backtrack(path)  # 재귀 호출
            path에서 선택을 제거  # 백트래킹