DFS/BFS - 백트래킹/최단경로

◼︎ 그래프탐색의 유형

1. 격자형

행렬처럼 n*m의 공간에 데이터가 입력된다
문제에 따라 상하좌우(4방향) 또는 대각선까지 포함한(8방향)으로 탐색한다

2. 정점형

한 순간의 상태를 정점으로 표현하고 상태전이를 간선으로 표현하여 그래프를 만들 수 있다
문제에 주어진 조건을 따라 정점을 만들어 나간다

DFS (Depth-First Search)

깊은 부분을 우선적으로 탐색하는 알고리즘
스택이나 재귀함수 이용
모든 노드를 방문할 경우 사용한다
문제에 제한이 있는 경우 가지치기와 백트래킹으로 경우를 줄일 수 있다
재귀함수를 사용할 경우 종료조건을 정확하게 명시해야 한다 (Base Case)
O(V+E)

def dfs(graph, v, visited):         # Stack이 아닌 Recursion 방식 사용
    # ★현재 노드 방문처리 후 출력
    visited[v] = True
    print(v, end=' ')

    # 현재 노드와 연결된 다른 노드를 재귀적 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 노드 정보 2차원 리스트
graph = [
    [],
    [2, 3],
    [4, 5],
    [6, 7],
    [2],
    [2],
    [3],
    [3]
]

visited = [False] * 8   # 방문처리 리스트
dfs(graph, 1, visited)  # 1번 노드에서 시작

백트래킹(Backtracking) 알고리즘

해를 찾는 도중에 지금 경로에서 해를 못 구할거 같으면 더이상 가지 않고 되돌아가 다른 경로를 선택해 해를 찾아가는 알고리즘
DFS(깊이 우선 탐색)을 기반으로 하는 알고리즘
가지치기를 통해 시간효율을 높여준다
- 가지치기(Pruning) : 해를 찾는 도중에 해가 아닐시 바로 중단하여 진행하지 않는 것
최적화 문제와 결정 문제를 푸는데 사용된다
- 결정문제 : 해가 존재하는지 여부를 Yes or No 로 답하는 문제
DFS vs 백트래킹
- DFS : 반드시 모든 노드를 거친다
- 백트래킹 : 가능성이 있는 노드만 거친다

N-Queen 문제

BFS (Breath-First Search)

같은 레벨을 우선적으로 탐색하는 알고리즘
큐 이용
노드 사이의 최단경로를 찾을 경우 사용한다
O(V+E)

from collections import deque

def bfs(graph, start, visited):     # Queue 사용
    # 시작 노드 큐에 삽입 후 방문처리
    queue = deque([start])
    visited[start] = True

    # 큐가 빌때까지 반복
    while queue:
        # ★큐에서 꺼내서 출력
        v = queue.popleft()
        print(v, end=' ')

        # 현재 노드와 연결된 다른 노드 중 아직 방문하지 않은 원소 큐에 삽입 후 방문처리
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 노드 정보 2차원 리스트
graph = [
    [],
    [2, 3],
    [4, 5],
    [6, 7],
    [2],
    [2],
    [3],
    [3]
]

visited = [False] * 8   # 방문처리 리스트
bfs(graph, 1, visited)  # 1번 노드에서 시작

최단경로(Shortest Path) 알고리즘

정점을 연결하는 다양한 경로 중 간선의 가중치 합이 가장 작은 경로를 찾는 알고리즘

1. 다익스트라 알고리즘

어느 노드(출발지)에서 다른 노드들까지 도달하는 최단거리를 구하는 알고리즘
가중치가 모두 음수가 아닐 때 사용
힙 사용 : O(ElogV)

2. 플로이드 워셜 알고리즘

그래프에 존재하는 모든 노드 쌍의 최단거리를 모두 구하는 알고리즘 (2차원)
O(V³)

3. 벨만-포드 알고리즘

어느 노드(출발지)에서 다른 노드들까지 도달하는 최단거리를 구하는 알고리즘
가중치에 음수가 존재할 때 사용
음수 순환이 존재 : 순환을 반복하면 가중치를 줄일 수 있다.
O(VE)

DFS/BFS 비교

DFS	BFS
스택 or 재귀함수	큐
모든노드 방문시 사용	최단경로
더 간단	더 복잡
느림	빠름

◼︎ DFS와 BFS 선택 방법

(1) 모든 정점을 방문하는 문제 : DFS와 BFS 모두 선택 가능
(2) 경로의 특징을 저장하는 문제 : DFS 사용
- 각 정점에 숫자가 적혀있고 a~b경로에 같은 숫자가 있으면 안된다는 등 특징을 저장해야 하는 문제
(3) 최단거리 문제 : 미로 찾기 등의 최단거리를 구하는 문제는 BFS 사용