[백준] 백준 문제 풀이 - 11724 연결요소의 갯수

👩🏻‍💻 문제링크

https://www.acmicpc.net/problem/11724

 

11724번: 연결 요소의 개수

 

✍️ 아이디어

1. 문제 이해

• 탐색이 진행되는 횟수를 기록 해야 함
• 처음에 while로 구현 하려다가 시간초과남

2. 무조건 dfs/bfs 문제는 방문일지를 만들자 ( 안만들고는 자꾸 에러가 난다 )

 

✍️소스코드

<나의 코드 - bfs 풀이 + 배열기반>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int graph[1001][1001]={0};
int visit[1001]={0};
int N;
int M; 
void bfs(int num)
{
	int n;
	queue <int> q; q.push(num);
	visit[num]=1;
	while(!q.empty())
	{
		n=q.front();
		q.pop();
		for(int m=1; m<N+1; m++)
		{
			if(graph[n][m]==1 && visit[m]==0)
			{
				visit[m]=1;
				q.push(m);
			}
		}
	}
}


int main()
{
	cin>>N;
	cin>>M;
	
	for(int i=0; i<M; i++)
	{
		int u,v;
		cin>>u>>v;
		graph[u][v]=1;
		graph[v][u]=1;
	}

	int result=0;
	for(int i=1; i<N+1; i++)
	{
		if(visit[i]!=1)
		{
			result++;
			bfs(i);
		}
	}
	cout<<result;
}

 

 

 

 

 

체감난이도	걸린시간	참고	사용 문법
하	50min	x	dfs/bfs