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

▶ 문제 : https://www.acmicpc.net/problem/1389

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

 

▶ 코드 :

let input = require('fs').readFileSync(`Computer Science/Alogrithms/백준JS/testCase.txt`).toString().split('\n');

const [n, m] = input[0].split(' ').map(num => parseInt(num))

let kevin = Infinity;
let answer = 0;
let graph = Array.from(new Array(n+1).fill(new Array()));

for (let i = 1; i<= m; i++){
    const [node1,node2] = input[i].split(' ').map(num => parseInt(num));
    
    graph[node1] = [...graph[node1], node2];
    graph[node2] = [...graph[node2], node1];
}

for (let i = 1; i<= n; i++){
    let temp = BFS(graph, i, n);
    
    if(kevin > temp){
        kevin = temp;
        answer = i;
    }
}

console.log(answer);



function BFS(graph,startNum, n){   
    let kevinNum = 0;

    let q = [[startNum,0]];
    let visited = Array(n+1).fill(false);
    
    while (q.length != 0){
        let [v, count] = q.shift();

        if(visited[v] === false){
            graph[v].map(num => {q.push([num, count+1])});
            visited[v] = true;
            kevinNum += count;
        }
    }
    
    return kevinNum;
}

 

▶ 문제 풀이 :

1. 그래프 탐색을 이용해야 한다는 점을 염두했으며, 각각의 노드는 양방향 연결되어있다.

2. 초기 양방향 연결을 위해 for문으로 입력을 처리하여 그래프를 생성하였다.

3. function BFS를 선언하였다.

  3-1. 인자로는 graph, startNum, n(사람의 수) 를 입력 받는다.

  3-2. BFS는 startNum에서부터 각각의 사람들을 모두 만나기까지 반복한다.

  3-3. 노드를 탐색하며 queue에 해당 노드의 번호와 해당 노드까지의 count를 저장하며, 각각의 노드를 처음 방문할때마다 kevinNum에 더해준다. => BFS는 루트 노드로부터 하위 노드까지의 최단거리를 구할 수 있기 때문에 count를 비교할 로직은 별도로 필요가 없다.

4. BFS 함수를 이용해 주어진 사람의 수 만큼(이때 사람의 번호는 1부터 시작) 반복하며 가장 작은 값의 케빈 베이컨 수를 가진 사람의 번호를 answer에 저장한다.

5. 이후 answer를 출력하면 끄읕!