깊이 우선 탐색(DFS : Depth First Search) 너비 우선 탐색은 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 입니다. FIFO(First In First Out) 방식으로 큐를 이용하여 구현하며 탐색 시작 노드와 가까운 노드를 우선하여 탐색하기 때문에 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장합니다. 장단점 장점 시작 노드부터 목표 노드 까지의 최단 경로를 보장 단점 큐를 이용해 다음에 탐색 할 노드를 저장하기 때문에 노드의 수가 많을 수로 많은 저장 공간을 필요로함 노드의 수가 늘어나면 탐색해야 하는 노드가 많아지기 때문에 비효율적 구현 방법 BFS를 사용하기 위해서는 먼저 그래프를..
그래프의 연결관계를 나타내는 방식은 인접 행렬과 인접 리스트로 두 가지의 방법이 있습니다. 인접 행렬(Adjacency Matrix) 인접 행렬은 이차원 배열을 이용하여 그래프를 표현하는 방식입니다. 위 의 그림과 같이 2 차원 배열의 형태로 두 노드의 번호를 좌표로 이용하여 1이면 연결이 되었음을 0이면 연결 되지 않았음을 뜻하게 됩니다. 무방향 그래프의 경우 양방향으로 연결 되기 때문에 아래와 같이 두 좌표에 입력을 합니다. graph[i][j] = 1 graph[j][i] = 1 방향 그래프의 경우 한쪽에서만 연결 되기 때문에 한 좌표에만 입력을 합니다. graph[i][j] = 1 장단점 장점 구현이 쉬움 노드의 연결성을 확인할 때 시간 복잡도는 O(1)로 빠름 단점 간선의 수와 상관 없이 항상 ..
깊이 우선 탐색(DFS : Depth First Search) 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나입니다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 입니다. 구현은 재귀 함수, 스택을 이용하며 시간 복잡도는 O(V + E) V = 노드 수, E = 엣지 수 입니다. 장단점 장점 현 경로상의 노드들만 기억하면 되기때문에 저장 공간의 수요가 적음 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음 단점 해가 없는 경로에 깊이 빠질 가능성이 있음 얻어진 해가 최단 경로가 된다는 보장이 없음 구현 방법 DFS를 사용하기 위해서는 먼저 그래프를 구현 해야합니다. 그래프를 ..
