백준 5567

백준 5567 : 결혼식

1. 그래프를 이용해 풀이하면 된다.
2. 연결 관계를 인접행렬로 만들고, 만약에 DFS로 풀이한다면 아래와 같은 경우에

1번이 상근이라고 가정하면, 2번 3번을 방문한다.
그 후 3번을 통해 4번을 가야 하는데 3번은 바로 위에서 이미 방문했으므로 건너뛰게 된다 -> 4번이 탐색이 안된다.

따라서 BFS로 풀이해야 한다.

정답 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

int n, m;
int rel[501][501], visited[501];
int cnt;


int main() {	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	//input
	cin>>n>>m;
	for(int i=0; i<m; i++) {
		int a, b; 
		cin>>a>>b;
		rel[a][b]=1;
		rel[b][a]=1;
	}
	
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			cout<<rel[i][j]<<' ';
		}
		
		cout<<'\n';
	}
	
	
	queue<pair<int, int>> q; //{nodeNumber, depth}
	visited[1] = 1; //sang geun
	q.push({1, 0});
	
	while(q.size()) {
		int node, depth;
		tie(node, depth) = q.front();
		q.pop();
		
		if(depth==2) { //if friend's friend
			continue;
		}
		
		for(int i=0; i<=n; i++) {
			if(rel[node][i] && !visited[i]) {
				visited[i] = 1;
				cnt++;
				q.push({i, depth+1});
			}
			
		}
	}
	
	cout<<cnt<<'\n';

	return 0;
}