백준 5567 결혼식(c++)

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

5567번: 결혼식

<코드>

#include <iostream>
using namespace std;
int board[501][501];
bool visited[501];
int cnt=0;
int n,m; // n => 정점의 최대 수 m=> 간선의 수 
void bfs(int node)
{
	for(int i=2;i<=n;i++)
	{
		if(board[1][i])
		{
			visited[i] = true;
			for(int j=2;j<=n;j++)
			{
				if(board[i][j]){
					visited[j] = true;
				}
			}
		}
	}
}
int main()
{
	
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int a,b; 
		cin>>a>>b;
		board[a][b] = board[b][a] = 1;
	}

	bfs(1);
	for(int i=2;i<=n;i++)
	{
		if(visited[i]) cnt++;
	}
	cout<<cnt<<'\n';
}

<문제 풀이>

우선적으로 상근이의 번호는 1번이다. 그래서 첫 번째로 1번 노드와 연관이 있는지 조사해야 된다.

그 부분이 board[1][i]이다.

그 이후 1번 노드를 제외한 노드(if문을 통해 이미 1번과 연관되있음을 확인했음)가 다른 노드와 연관 되어있는지 확인해주면 된다.  

<코드 참조>

https://jow1025.tistory.com/92

[백준 5567] 결혼식