1. 그래프 순회 - 그래프 순회란 정점과 에지를 체계적으로 방문하는 것을 말한다. ⓐ 깊이 우선 탐색(depth first search_DFS) : 전순위 순회 일반화 ⓑ 너비 우선 탐색(Breadth first search_BFS) : 레벨순위 순회 일반화 2. 깊이 우선 탐색(DFS) 1) 알고리즘 ① 먼저 정점 v를 방문 한 다음 ② v에 인접한 정점 중에서 방문하지 않는 정점 w를 찾아서 w에 대한 DFS를 재귀적으로 수행한다. 2) 구현 #include #include using namespace std; #define MAX_NODE 100 bool visited[MAX_NODE]; vector v[MAX_NODE]; void DFS(int x){ visited[x] = true; print..
dfs
11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 난이도 : 실버2 문제 설명 : 연결 요소란, 무방향 그래프에서 적어도 한 개 이상의 경로로 연결된 정점들로 구성된 종속 그래프를 이야기합니다. 예를 들어, 아래와 같은 그림이 있을 때, 연결 요소의 개수는 2개입니다. (각각의 떨어져 있는 그래프가 2개!) 풀이 과정 : DFS나 BFS로 풀 수있는 문제입니다. 이 문제를 풀기 전에 dfs와 b..
1. DFS란? - DFS 는 깊이 우선 탐색 을 말합니다. - 루트 노드에서 시작하여, 해당 노드들의 자식을 우선적으로 탐색합니다. * 미로찾기로 예시를 들면, 한 방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게 되면 다시 가까운 갈림길로 되돌아 와서 다시 탐색을 진행하는 것과 유사합니다. Q. 깊이우선 탐색을 하면 순서가 어떻게 될까요? A. 0-1-3-4-2-5-6 1) 특징 > 모든 노드를 탐색할 때 좋은 방법입니다. > BFS보다 좀 더 간단하지만 느립니다. 2) 알고리즘 구현 방법 DFS의 결과 : 1 - 2 - 3 - 5 - 4 -6 ⓐ 재귀함수 이용 #include #include using namespace std; bool visited[10]; //방문했던 노드를 기억하는..
