문제 간단설명
이 문제는 두 사람이 몇 단계 이내에 친구의 친구로 이어질 수 있는지를 나타내는 케빈 베이컨의 수를 계산하고, 케빈 베이컨의 수가 가장 작은 사람을 찾는 문제입니다. 각 사람마다 다른 모든 사람들과 최소 단계로 이어지는 경로를 구한 뒤, 그 경로의 단계 수를 모두 더하여 케빈 베이컨의 수를 계산합니다. 예를 들어, 사람 A와 B가 최소 3단계로 연결된다면, A의 케빈 베이컨 수에는 3이 포함됩니다. 모든 유저의 케빈 베이컨 수를 계산한 뒤, 그 값이 가장 작은 사람을 찾는 것이 문제의 목표입니다.
제한 사항
- 2 <= N <= 100
- 1 <= M <= 5000
- 입력 관계:
- 입력은 각 친구 관계를 나타내며, (A, B) 형식으로 주어집니다.
- 중복된 친구 관계가 존재할 수 있으며, 자기 자신과 친구인 관계는 없습니다.
- 모든 사람은 친구 관계로 이어져 있으며, 단절된 그룹은 없습니다.
성공 코드
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
.readFileSync(filePath)
.toString()
.trim()
.split('\n')
.map((el) => el.trim());
const [N, M] = input.shift().split(' ').map(Number);
const relationList = input.map((row) => row.split(' ').map(Number));
// 인접 행렬
const adjList = {};
// 케빈 베이컨 카운트 인접 행렬
const kevinBaconCountAdjList = Array.from({ length: N + 1 }, () =>
new Array(N + 1).fill(0)
);
function solution() {
initAdjList();
const kevinBaconCountList = getKevinBaconCountList();
const result = getResult(kevinBaconCountList);
console.log(result);
}
/**
* 인접행렬을 초기화 해주는 함수이다.
*/
function initAdjList() {
for (let i = 1; i <= N; i++) {
adjList[i] = new Set();
}
for (const [user1, user2] of relationList) {
adjList[user1].add(user2);
adjList[user2].add(user1);
}
}
/**
* bfs를 이용해 각 노드까지의 단계를 구하는 함수이다.
*
* @param {number} start 시작 노드
*/
function bfs(start) {
const queue = [[start, 1]];
const visited = Array.from({ length: N + 1 }, () => false);
visited[start] = true;
while (queue.length > 0) {
const [curUser, curCount] = queue.shift();
for (const adjUser of adjList[curUser]) {
if (visited[adjUser]) {
continue;
}
kevinBaconCountAdjList[curUser][adjUser] = 1;
kevinBaconCountAdjList[start][adjUser] = curCount;
visited[adjUser] = true;
queue.push([adjUser, curCount + 1]);
}
}
}
/**
* 각 유저별 케빈 베이컨수를 구하는 함수이다.
*
* @returns 각 유저별 케빈 베이컨수가 담긴 배열
*/
function getKevinBaconCountList() {
for (let i = 1; i <= N; i++) {
bfs(i);
}
const kevinBaconCountList = kevinBaconCountAdjList.map((row) =>
row.reduce((acc, cur) => acc + cur)
);
return kevinBaconCountList;
}
/**
* 케빈 베이컨의 수가 가장 작은 사람을 구하는 함수이다.
*
* @param {number[]} kevinBaconCountList
* @returns 케빈 베이커의 수가 가장 작은 사람
*/
function getResult(kevinBaconCountList) {
const min = Math.min(...kevinBaconCountList.slice(1));
const minIndex = kevinBaconCountList.indexOf(min);
return minIndex;
}
solution();
인접 리스트를 이용해 문제에서 요구한 그대로 bfs로 구현하였다.
주의할 점은, 중복된 관계도 들어올 수 있기 때문에 Set 자료구조를 사용했다.
'PS > 백준' 카테고리의 다른 글
백준 / 문자열 / 5525번 / IOIOI / JS (0) | 2024.11.09 |
---|---|
백준 / 구현 / 5430번 / AC / JS (0) | 2024.11.08 |
백준 / 그래프 / 14940번 / 쉬운 최단거리 / JS (0) | 2024.11.06 |
백준 / 재귀 / 12919번 / A와 B 2 / JS (1) | 2024.10.24 |