[1389] 케빈 베이컨의 6단계 법칙 - BFS, 플로이드 와샬 ★★☆ /복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

---

[ 문제 접근 ]

 

BFS 문제라고 생각해내는건 어렵지 않은 문제. 다만, 플로이드 와샬로 풀면 더 빠를거 같은데.. 하는 의구심은 든다.

 

---

[ 최종 코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using std::cout; using std::cin;
using std::vector;
 
int n, m;
vector<int> friends[101];
int visited[101];
int answer[101];
 
void dfsAll(int start) {
	std::queue<int> que;
	que.push(start);
	visited[start]++;
	while (!que.empty()) {
		int cur = que.front();
		que.pop();
		for (size_t i = 0; i < friends[cur].size(); i++) {
			int next = friends[cur][i];
			if (visited[next]<0) {
				que.push(next);
				visited[next] = visited[cur] + 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		answer[start] += visited[i];  // 어짜피 자기 자신의 값은 0이라 더해줘도 상관없다.
	}
}
void resetVisited() {
	std::fill_n(visited+1, n, -1);
}
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	int x, y;
	while (m--) {
		cin >> x >> y;
		friends[x].push_back(y);
		friends[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) { // 모든 노드에 대해서 DFS
		resetVisited();  // visited 초기화
		dfsAll(i);
	}
	cout << std::min_element(answer+1, answer+1 + n)-answer;
	return 0;
}

---

[ Key Point ]

 

👉 모든 노드에 대해서 DFS를 해줘야 하기 때문에 visited 배열을 초기화 해줘야한다.

void resetVisited() {
	std::fill_n(visited+1, n, -1);
}

 

👉 최솟값의 index를 구하기 위해서는' min_element( arr, arr+5) - arr ' 처럼 마지막에 arr의 처음 index를 빼줘야한다.

std::min_element(answer+1, answer+1 + n)-answer;

---

[ 다른 사람 풀이 ]

 

플로이드 와샬로 풀었는데 그래프를 인접 행렬로 받았다.

​

복습할때 꼭 이렇게 풀어보자.!!

 

ref : http://https://yabmoons.tistory.com/32