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

📎Problem Link

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

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

 

📋 문제 정리

• 케빈 베이컨의 6단계 법칙 : 지구의 모든 사람들은 6다리를 걸쳐 이어져 있다!
• 케빈 베이컨의 수가 가장 작은 사람 찾기, 여러명일 시 번호가 제일 작은 사람으로 출력
• 첫째 줄에는 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000) 입력
• 둘째 줄부터 M개의 줄에는 친구 관계 입력
• 친구가 한명도 없는 사람은 없음
• 사람 번호는 1번부터 N번까지!

📌 예제 1

예제의 일부를 그림으로 나타내면 다음과 같다. 1에서 2, 3, 4, 5로 갈 수 있는 최단 거리를 각각 구하고 다 더한 값이 바로 케빈 베이컨의 수다. 2, 3, 4, 5에 대한 케빈 베이컨의 수도 위와 같이 계산하면 사람 3과 사람 5의 케빈 베이컨의 수가 5로 제일 적고, 여러 명일 시 번호가 제일 작은 사람만 출력하기 때문에 3을 출력한다.

 

🧐 Idea

• 사람 A에서 사람 B로 갈 수 있는 모든 경우를 탐색하고 count 값을 비교하며 최솟값을 구해야함.
• DFS 함수로 탐색을 진행할 때, DFS를 처음에 시작한 start 점을 기준으로 하여 count
• DFS 재귀 함수를 하나씩 빠져나올 때 이전의 count 값으로 돌아가야함.

---

💻 Code

int main() {
	Kebin bacon;
	vector <int> sum;

	cin >> bacon.N >> bacon.M;
	for (int i = 0; i < bacon.M; i++) {
		int f1, f2;
		cin >> f1 >> f2;
		bacon.v[f1].push_back(f2);
		bacon.v[f2].push_back(f1);
	}

	for (int i = 1; i <= bacon.N; i++) {
		bacon.DFS(i, i, 0);
		memset(bacon.visited, 0, sizeof(bacon.visited));
	}

	for (int i = 1; i <= bacon.N; i++) {
		int s=0;
		for (int j = 1; j <= bacon.N; j++) {
			
			s += bacon.answer[i][j];
		}
		sum.push_back(s);
	}
	cout << min_element(sum.begin(), sum.end())-sum.begin()+1;
}

먼저 사람의 수와 사람 관계 수를 입력 받고, 사람 관계 수만큼 관계를 입력받아 각 사람마다 연결된 관계들을 vector에 입력한다. 이 때, 관계는 양방향이기 때문에 두 사람 모두에게 값을 넣어준다.

모든 사람에 대해 DFS함수를 돌려 케빈 베이컨의 수를 구하기 위한 각 관계에 대한 최소 연결 값을 구한다.

모든 사람에 대한 탐색이 끝나면 예제와 같이 모든 값을 더하여 각 사람 마다의 케빈 베이컨의 수를 구한다.

min_element 함수를 통하여 최소 값을 갖는 첫번째 인덱스를 출력한다. (+1을 해준 이유는 index가 사람 번호보다 1 적게 나오기 때문에!)

 

void DFS(int start, int currentnode, int count){
		visited[currentnode] = 1;

		for (int i = 0; i < v[currentnode].size(); i++) {
			int nextnode = v[currentnode][i];

			if (!visited[nextnode]) {
				if (!answer[start][nextnode])
					answer[start][nextnode] = ++count;
				else
					answer[start][nextnode] = min(answer[start][nextnode], ++count);

				DFS(start, nextnode, count);
				count--;
			}
				
		}
		visited[currentnode] = 0;
	}

이번 DFS 함수는 이전과 다른 점이 있다면 시작 번호, 다음 사람 번호, 그리고 관계 수를 count한 값을 인자로 입력했다.

start : 시작 점인 사람과 연결된 모든 관계를 탐색하는 것이기 때문에 각 관계의 연결 수를 구해 answer 이중 배열에 저장하려면 start 값이 필요하다.

nextnode : nextnode의 경우 DFS 함수로 넘어가면 currentnode가 된다. 넘겨받은 currentnode에 대한 탐색을 진행함으로써 start부터 이어진 관계를 탐색할 수 있게 한다.

count : 예를 들어 A-B-C, A-B-D라는 관계가 있다고 가정하자. A-B-C까지 탐색을 모두 진행했을 경우 count는 2가 될것이다. A-B-D 탐색도 진행하려면 B로 다시 돌아가 D까지 다시 count를 해야하는데 count를 그대로 사용한다면 count는 3이 될것이다. 그러므로 B의 count 값을 온전히 사용하기 위해서 count를 지역변수로 사용할 수 있게끔 설정했다.

 

for문안의 두번째 if문을 살펴보자. 만약 관계 (start, nextnode)에 대한 answer 배열 값이 0이라면 이 관계에 대한 탐색이 아직 한번도 없었다는 뜻이기 때문에 ++count를 입력해주고, 0이 아니라면 탐색된 적이 있다는 뜻이기 때문에 이전의 탐색 값과 현재의 탐색 값을 비교하여 최솟값을 입력하도록 해줬다.

 

DFS함수가 끝날 때는 currentnode에 대한 visited 값을 0으로 변경함으로써 다른 경로 탐색에 지장이 없도록 한다.

 

 

---