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

 

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

소스결과 : 1996 KB / 0 ms

출처 : Backjoon

언어 : C++17

 

설명

케빈 베이컨의 여섯다리 : 위키백과_케빈 베이컨의 여섯다리

를 구현하는 문제

 

한 사람을 기준으로 친구 관계에 있는 사람들을 이어나가 몇 다리만에 그 사람과 연관이 있어지는지 확인 하는 문제

문제에서는 6단계의 법칙이라 했지만 검색을 하면 여섯다리로 나온다

자세한 내용은 위 링크를 참조, 또는 위 링크의 출처를 참조

DFS를 사용하면 손쉽게 결과가 구해진다.

 

몇가지 주의 할 점이라면 방문한 사람을 다시 방문해야 하는 경우가 존재 한다

예를들어 1 -> 2 -> 4 -> 5 의 경우 거리는 3이 되지만 동시에 1 -> 5 라면 거리를 1로 수정해야 하는 경우가 존재한다.

따라서 방문 했다고 해서 재 방문을 막으면 오답이 된다.

위 경우는 백준 문제의 예시에서도 참고 할 수 있다.

 

알고리즘

1. 100 by 100 의 인접 행렬을 생성

2. 1을 기준으로 n 까지 dfs 를 진행 ( 소스코드에서는 0 ~ n -1 )

3. 각 지점과의 거리를 합산 후 베이컨 거리를 저장하는 배열에 저장

4. 현재 까지의 최소 거리와 비교 후 최소 거리 갱신

5. 1 ~ n 까지 최소 거리를 가진 인덱스를 1개만 출력

 

소스코드

#include <iostream>

using namespace std;

bool adjMap[100][100];
int bacon[100];
int n;

void dfs(int num, int cnt, int checker[100])
{
	checker[num] = cnt;

	for (int i = 0; i < n; i++)
		if (adjMap[num][i] && checker[i] == -1)
			dfs(i, cnt + 1, checker);
		else if (adjMap[num][i] && checker[i] > cnt + 1)
			dfs(i, cnt + 1, checker);
}

int main()
{
	int m;
	int min = 100000;
	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		short x, y;
		cin >> x >> y;
		adjMap[x-1][y-1] = adjMap[y-1][x-1] = true;
	}

	for (int i = 0; i < n; i++)
	{
		int check[100];
		fill_n(check, n, -1);

		dfs(i, 0, check);

		for (int j = 0; j < n; j++)
			bacon[i] += check[j];

		if (min > bacon[i])
			min = bacon[i];
	}

	for (int i = 0; i < n; i++)
		if (min == bacon[i])
		{
			cout << i + 1;
			break;
		}
}