백준 1389 (실버 1) BFS, DFS 활용

 

해당 문제는 BFS, DFS를 활용하는 문제입니다

 

아래는 문제의 설명이다

 

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

 

 

풀이: for을 1부터 n까지 돌립니다 그리고 i값을 queue에 넣어줍니다 그리고 whlie 문으로 BFS를 탐색하면서 

방문하지 않은 숫자가 있다면 그 x의 방문한 순서에 +1을 하면 됩니다 

 

visit[x]+1을 하는 이유는 만약 (1과 연결 되어있는 숫자가 3, 4), (3과 연결되어 있는 숫자가 2), (4와 연결된 숫자가 5)라고 되어있다면

 

큐에 3 4 2 5 순서로 들어갈 것입니다, 그럼 1의 visit의 값은 1이고 3과 4는 1의 visit의 값에 +1을 하면 2가 됩니다

3과 연결되어 있는 2는 3이 2이기 때문에 visit값이 3이 되고 4와 연결되어 있는 5도 4의 visit값에 + 1을 한 3이 됩니다.

 

그렇다면 1은 1), 2는 3), 3은 2), 4는 2), 5는 3이 될겁니다 이 값을 모두 더하면 1 + 3 + 2 + 2 + 3 = 11이 됩니다 

뭔가 이상하지 않으신가요? 위에 설명대로라면 값이 6이 나와야하는데 말이죠

 

왜냐하면 저희는 visit의 시작을 0으로 시작하지 않고 1로 시작했기 때문에 그렇습니다

그럼 결국 n번을 모두 1부터 시작했으니 1을 n번 더한거나 마찬가지 입니다.

그냥 sum의 값에서 n을 빼시면 정상적인 결과가 나올 것 입니다. 

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;


int main(){
	
	vector<vector<int>> v(101);
	queue<int> Q;
	
	
	int n, m;
	
	cin >> n >> m;
	
	int x, y;
	
	for(int i = 0; i < m; i++){
		cin >> x >> y;
		
		v[x].push_back(y);
		v[y].push_back(x);
	}
	
	for(int i = 1; i <= n; i++){
		sort(v[i].begin(),v[i].end());
	}
	
	int min = 100000000;
	
	int c;
	
	int index = 0;
	
	for(int i = 1; i <= n; i++) {
		
		int sum = 0;
		
		int visit[101] = {0,};
	
		
		Q.push(i);
		
		visit[i] = 1;
		
		while(!Q.empty()){
			int x = Q.front(); Q.pop();
			
			for(int j = 0; j < v[x].size(); j++){
				if(visit[v[x][j]] > 0){
					continue;
				}
				
				Q.push(v[x][j]);
				visit[v[x][j]] = visit[x]+1;
			}
			
			count++;
		}
		
		
		for(int j = 1; j <= n; j++){
			sum+= visit[j];
		}
		
		sum = sum - n;
		
		if(min > sum) {
			min = sum;
			index = i;
		}
	}
	
	cout << index;
	
}