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

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

Note

케빈 베이컨의 여섯다리 : 위키백과_케빈 베이컨의 여섯다리
를 구현하는 문제

한 사람을 기준으로 친구 관계에 있는 사람들을 이어나가 몇 다리만에 그 사람과 연관이 있어지는지 확인 하는 문제
문제에서는 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;
		}
}

2019-01-06 17:36:11에 Tistory에서 작성되었습니다.