[백준] 11724 연결요소의 개수 C++ (BFS, DFS)
📌백준 11724 연결요소의 개수
https://www.acmicpc.net/problem/11724
그래프가 다 이어질 수도 있고 중간에 끊길 수도 있다.
이어지다가 끊기면 하나의 연결요소가 되는 것이다.
이 연결요소가 몇 개 있는지를 출력하는 문제이다.
DFS 함수는 연결된 요소들이 있으면 연속해서 호출된다. 그리고 더 이상 방문기록 없는 연결된 요소가 없으면 끝난다. 이어지다가 끊긴 것으로, 연결 요소 하나가 만들어졌다. 그리고 main()으로 돌아오는데, main()에서 인접리스트 요소 중 방문기록이 없으면 또 실행한다.
즉 main()에서 DFS를 실행할 때 연결요소 개수가 +1 되는 것이다.
BFS 함수는 큐가 빌 때까지 탐색한다. 즉 연결된 노드들을 탐색하고 끝나는 것이다. 이것도 DFS와 마찬가지로 더 이상 방문기록 없는 연결된 요소가 없으면 끝이나서 main()으로 돌아온다. 이때도 main()에서 BFS를 실행해줄 때 연결요소 개수가 +1 되는 것이다.
DFS 풀이
#include <iostream>
#include <vector>
using namespace std;
vector<int> vect[1001]; //인접리스트
int visited[1001]; //방문기록
int N, M;
/* DFS : 방문기록 남기는 용도 */
void DFS(int vertex)
{
visited[vertex] = 1;
for (int i = 0; i < vect[vertex].size(); i++) //최댓값 주의 : 벡터 그 원소에 해당하는 크기만큼 돌아야함
{
int idx = vect[vertex][i];
if (visited[idx] == 0)
{
DFS(idx);
}
}
}
int main()
{
int u, v;
int cnt = 0;
cin >> N >> M;
for (int i = 0; i < M; i++)
{
cin >> u >> v;
vect[u].push_back(v);
vect[v].push_back(u); //무방향 그래프이기 때문
}
for (int i = 1; i <= N; i++) //빠짐없이 탐색하기 위해
{
if (visited[i] == 0)
{
cnt++;
DFS(i);
}
}
cout << cnt << "\n";
}
BFS 풀이
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> vect[1001];
int visited[1001];
int N, M;
void BFS(int start)
{
queue<int> q;
q.push(start);
visited[start] = 1;
while (q.size() != 0)
{
// start가 아닌 가장 앞의 값에 인근 정점을 push 해줘야함
int current = q.front();
q.pop();
for (int i = 0; i < vect[current].size(); i++)
{
if (visited[vect[current][i]] == 0)
{
visited[vect[current][i]] = 1;
q.push(vect[current][i]);
//BFS는 재귀가 아니라서 큐에 push 해주는 동시에 방문기록 남겨야함.
}
}
}
}
int main()
{
int cnt = 0; //연결요소 개수 세는 변수
int u, v;
cin >> N >> M;
for (int i = 0; i < M; i++)
{
cin >> u >> v;
vect[u].push_back(v);
vect[v].push_back(u);
}
//빠짐없이 탐색하기 위해
for (int i = 1; i <= N; i++)
{
if (visited[i] == 0)
{
BFS(i);
cnt++;
}
}
cout << cnt;
}
Author And Source
이 문제에 관하여([백준] 11724 연결요소의 개수 C++ (BFS, DFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@matcha_/백준-11724-연결요소의-개수-C-BFS-DFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)