살구의 개발자 첫걸음을 위한

1. 연결 요소(11724번)1) 연결 요소(Connected Component) - 그래프가 아래 그림과 같이 연결되어 있지 않은 경우가 있을 수도 있다.- 이렇게 나누어진 각 각의 그래프를 연결 요소라고 한다.- 연결 요소는 해당 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.- 또, 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.- 아래 그래프는 총 2개의 연결 요소로 이루어져 있다.- 연결 요소를 구하는 것은 DFS나 BFS 탐색을 이용해서 구할 수 있다. 2) 정답 코드 #include #include using namespace std; vector a[1001];bool check[1001]; void dfs(int x) {check[x] = true;for (in..

1. 그래프의 탐색 - 목적 : 모든 정점을 1번씩 방문- DFS : 깊이 우선 탐색, 최대한 깊숙히 많이 방문, 재귀 또는 stack 구현- BFS : 너비 우선 탐색, 최대한 넓게 많이 방문, queue 구현, 모든 가중치가 1일 때 최단거리 구할 수 있음 2. 깊이 우선 탐색(Depth First Search) - 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 (stack에 push)- 갈 수 없으면 이전 정점으로 돌아간다. (stack에서 pop)- stack이 비면 탐색 종료- 재귀 호출을 이용해서도 구현할 수 있다. (예시 1) - 인접행렬, 재귀 호출void dfs(int x){check[x]=true;printf("%d", x);for(int i=1;i m >> s;for (int i..

1. 그래프의 표현(Representation of Graph) - 인접행렬, 인접리스트, 간선리스트- 아래와 같은 그래프는 정점이 6개, 간선이 8개 있다. - 간선에 방향이 없기 때문에, 방향이 없는 그래프이다.- 정점 : {1,2,3,4,5,6}- 간선 : {(1,2),(1,5),(2,5),(2,3),(3,4),(2,4),(4,5),(4,6)} 2. 인접 행렬(Adjacency Matrix)- 정점의 개수를 V라고 했을 때- V * V 크기의 이차원 배열을 이용한다.- A[i][j] = 1(i->j 간선이 있을 때), 0 없을 때 (예시1) - n개의 정점, m개의 간선, 가중치 없는 양방향 그래프#include using namespace std;int a[10][10];int main(void)..