Devlog

DFS (Depth First Search, 깊이 우선 탐색) 시작 정점으로부터 연결 된 노드를 따라 마지막 노드까지 탐색하는 알고리즘 특징 - 모든 노드를 탐색해야할 때 사용 - 재귀적 장점 - 구현이 BFS보다 간단하다. - 저장 공간이 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 - 단순 검색 속도가 BFS보다 느리다. - 목표까지의 경로가 여러 개인 경우 구한 해가 최적이 아닐 수 있다. - 해가 없는 경로에 깊이 빠질 가능성이 있다. -> 임의의 깊이까지 탐색할 때까지 목표를 찾지 못한다면 다음 경로를 찾을 수도.. Python 구현 코드 check = [0 for i in range(N)] # 방문 여부를 확인 s = [[0, 1, 1, 1], [1, ..

BFS (Breadth First Search, 너비 우선 탐색) 시작 정점으로부터 거리가 가까운 정점 순(너비 우선)으로 인접한 노드를 탐색하는 알고리즘 특징 - 최단 경로를 찾을 때 사용 - 일반적으로 큐(Queue) 사용 (선입선출 방식을 사용해야 함) - 재귀적 x - 시간복잡도 : 인접 리스트로 구현된 경우 O(|V|+|E|), 인접 행렬로 구현했을 경우 O(|V|^2) - 입력 : 노드의 갯수 n, 그래프 graph, 시작 노드 v 장점 - 최단 경로를 보장 - 단순 검색 속도가 DFS보다 빠르다. 단점 - 경로가 긴 경우 많은 메모리를 필요로 한다. Python 구현 코드 n = 6 graph = {1: [3, 2], 2: [3, 1, 4, 5], 3: [6, 4, 2, 1], 4: [3, ..