my devlog;

DFS 또는 BFS를 사용하여 연결 성분의 개수를 구하는 문제이다. 참고 : hyunah-home.tistory.com/entry/%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS%EC%99%80-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS-%EC%9D%91%EC%9A%A9-%EC%97%B0%EA%B2%B0-%EC%84%B1%EB%B6%84-%EC%B0%BE%EA%B8%B0 #include #include using namespace std; int visited[201]; int answer; void dfs(int v, vector computers){ visited[v] = answe..

그래프 탐색 : 그래프의 기본 연산 중 하나. 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문. 특정 정점에서 특정 정점까지 갈 수 있는지 없는지를 탐색 1. 깊이우선 탐색(DFS) ○ 개념 : 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 방향으로 다시 탐색을 진행. 갈림길로 다시 돌아가는 과정에서는 스택을 사용하거나 재귀 함수 호출을 이용. ○ 알고리즘 : 정점 v를 방문한 후 해당 정점이 방문되었다고 표시하고 v의 모든 인접 정점에 대해 방문되지 않은 정점이라면 재귀 함수 호출. ○ 프로그램 int visited[8]; vector adj_list[8]; //adj_list[i]에는 i의 인접 정점들의 리스..

DFS와 BFS를 구현하는 연습을 해볼 수 있는 기본 문제. 주의해야 할 점 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문. 2. 입력으로 주어지는 간선은 양방향. 3. 간선이 없는 노드. 더 이상 방문할 수 있는 점이 없는 경우 종료되기 때문에, 어떠한 노드와도 연결되어 있지 않은 노드는 따로 처리해줄 필요가 없다. #include #include #include #include #include using namespace std; int c[1001]; //정점에 방문했는지 체크하는 배열 vector a[1001]; //그래프 정보 저장하는 벡터 //처음 그래프를 구성할 때에 에지를 추가하는 함수 void insert_edge(int i, int j) { a[i]...