.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
BFS, 플로이드-와샬
문제
케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.
예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?
천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.
케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.
오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.
예를 들어, 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이다.
5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.
BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.
출력
첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.
예제 입력 1
5 5
1 3
1 4
4 5
4 3
3 2
Plain Text
복사
예제 출력 1
3
Plain Text
복사
My solution
위의 블로그를 참조해서 알고리즘을 다시 익힌다음 문제를 풀었다.
플로이드 와샬 알고리즘은 최단 경로를 구하는 알고리즘으로 각 정점은 다른 정점과 연결된 edge에 비용이 할당되어 있다. 이 비용들을 가지고 어떤 정점을 거쳐서 다른 정점으로 가는 최단 비용을 구하는 것이다.
중요한 것은 처음에 주어진 비용으로 이차원 배열을 초기화시켜놓는 것이다. 모든 값이 Infinity(경로 없음)으로 초기화된 이차원 배열에 입력으로 주어진 비용을 넣어 초기화한다.
function solution(i) {
const input = i.toString().trim().split('\n');
const [N, M] = input[0].split(' ');
input.shift();
const arr = [];
for (const x of input) {
arr.push(x.split(' ').map(v => v - 1));
}
const adjArr = [...Array(+N)].fill(Infinity).map(() => [...Array(+N)].fill(Infinity));
for (const x of arr) {
adjArr[x[0]][x[1]] = 1;
adjArr[x[1]][x[0]] = 1;
}
JavaScript
복사
그 다음 플로이드 와샬 함수에 인접행렬(비용으로 구성된 이차원배열)을 전달한다.
이 함수에서는 먼저 이중 for문을 돌면서 노드가 자기 자신으로 이동하는 경로가 없으므로(1 1, 2 2) 0으로 초기화해주는 로직을 수행한다.
1, 2 2) 0으로 초기화해주는 로직을 수행한다.그 다음 삼중 for문을 통해서 x에서 y로 이동하는 최단 비용과 x에서 노드 1로 이동하는 비용 + y에서 노드 1로 이동하는 비용을 비교한다음 그중 최솟값으로 업데이트해준다.
우리가 전달한 배열은 우선 중간 노드를 거쳐서 다른 노드에 이동하는 것은 비용에 산정되어 있지 않으므로 플로이드 와샬 알고리즘이 어떤 중간 노드를 거쳐서 다른 노드로 이동하는 것을 고려해서 비용을 산정해주어 Infinity(경로없음)으로 할당된 원소도 이 알고리즘을 거치면 어떠한 비용을 할당 받을수도 있게 된다.
또한, 노드 3에서 4로 이동하고자 할 때 최단 비용을 구하기 위해서 노드 3에서 4로 이동하는 비용은 1로 할당되어 있지만 노드 3에서 노드1로 가는 비용과 노드 1에서 노드4로 가는 비용을 합친 비용이 기존의 노드 3에서 노드 4로 가는 비용보다 적을수도 있다. (이 문제에서는 비용이 1로 고정이므로 그럴 일은 없다.)
이렇게 알고리즘을 거친 다음 배열은 어떤 한 노드에서 다른 노드로 이동하는 최단경로를 통한 최단비용이 할당되어있는 아래의 상태가 된다.
그럼 여기서 최단 비용(케빈 베이컨의 수가 최소)을 가진 사람은 누구인지 구해야 한다.
answer라는 배열에 최단비용을 Infinity로 초기화해서 최솟값을 담아줄 준비를 하고, 1번 인덱스에 몇 번 사람인지 담기도록 했는데, 어차피 아니라면 바뀔 것이므로 1번 사람을 넣어 초기화했다.
i번째 사람부터 N번째 사람까지 이차원 배열의 행(배열)에 있는 값을 자기자신으로 가는 것 빼고 모두 더해서 sum을 구했다. 이 sum이 케빈 베이컨의 수이다.
따라서 sum을 가지고 answer에 들어있는 값과 비교해서 최솟값일 때 교체해준다.
let answer = [Infinity, 1];
for (let i = 0; i < +N; i++) {
const sum = [0, i + 1];
for (let j = 0; j < +N; j++) if (i !== j) sum[0] += adjArr[i][j];
if (sum[0] < answer[0]) answer = sum;
}
JavaScript
복사
처음에 제출할 때 계속 런타임 에러가 떠서 재귀 호출도 안 썼고, 혹시 변수를 선언하지 않고 사용한 것이 있나 했다. 근데 계속 고치다가 다시 제출해보니 잘 제출되어서 로직을 바꾼게 없는데 이해가 되지 않았지만 프로그래머스에서는 거의 이럴 일이 없으므로 넘어간다.
플로이드 와샬 알고리즘이 매우 간단한 알고리즘인데 그동안 잊어버리고 있어서 다시 한번 되새길 수 있었던 기초 문제였다. 기본 bfs문제라고도 하는데 bfs만으로 푸는 것도 시도해보면 좋겠다는 생각이 든다. 개인적으로 bfs가 익숙하지 않기 때문이다. 그래프 문제는 거의 단골 문제이기 때문에 그래프에 더 많은 시간을 투자해야한다.
소스코드
function floyd(arr, n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i === j) arr[i][j] = 0;
}
}
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
}
function solution(i) {
const input = i.toString().trim().split('\n');
const firstLine = input[0].split(' ');
const N = firstLine[0];
input.shift();
const inputArr = [];
for (const x of input) inputArr.push(x.split(' ').map(v => v - 1));
// 유저의 수만큼 이차원 배열의 길이를 잡고 만듦
const adjArr = [...Array(+N)].fill(Infinity).map(() => [...Array(+N)].fill(Infinity));
for (const x of inputArr) {
adjArr[x[0]][x[1]] = 1;
adjArr[x[1]][x[0]] = 1;
}
floyd(adjArr, N);
let answer = [Infinity, 1];
for (let i = 0; i < +N; i++) {
const sum = [0, i + 1];
for (let j = 0; j < +N; j++) if (i !== j) sum[0] += adjArr[i][j];
if (sum[0] < answer[0]) answer = sum;
}
console.log(answer[1]);
return answer[1].toString();
}
test('solution', () => {
expect(
solution(`5 5
1 3
1 4
4 5
4 3
3 2
`)
).toStrictEqual('3');
expect(
solution(`5 4
3 1
2 3
1 4
5 2
`)
).toStrictEqual('3');
expect(
solution(`
5 7
1 2
1 3
2 3
2 4
3 4
3 5
4 5
`)
).toStrictEqual('3');
});
JavaScript
복사
