[취업준비일지] - 136

 

 

(1).백준 1389 케빈 베이컨의 6단계 법칙이라는 문제는
이름처럼 케빈 베이컨의 법칙을 통해 존재하는 모든 사람(주어진 그래프)과의 단계 합을 구하는 문제로
모든 사람과 연결되어있다면 사람의 숫자 -1(본인제외)의 결고가 나온다고 볼 수 있다.

대충 감은 왔지만 조금 복잡해보여서 알고리즘 분류 힌트를 살짝 보니
플로이드-워셜이라는 알고리즘을 사용해야 한다고 한다.

플로이드-워셜을 검색해보니 다익스트라 알고리즘이 사용된 느낌이지만
시작점을 하나로 고정하는 것이 아닌 각각의 루트를 모두 탐색해야 하기 때문에
연결된 점을 모두 1(거리)로 표기하고 

각각의 노드들을 징검다리로 설정해
그 징검다리를 통과하는 노드들을 다시 해당 징검다리의 거리 +1로 설정하는 방식으로
모든 노드가 연결되게 진행한다.

이 방식은 O(N^3)의 시간복잡도를 가지기 때문에
지나치게 많은 인물의 관계를 계산할 수는 없다고 한다.

해당 방식을 구현하기 위해 matrix를 초기화했으며 
중복된 값이 들어갈 경우 최소값이 들어가게 Math.min을 사용하고 싶었기 때문에
초기값을 주어진 조건의 최대치보다 큰 100으로 설정했다.

자기 자신은 0, 연결된 곳은 1로 다시 입력된 값들을 처리하고
마지막으로 1부터 n까지 각각을 중간점으로 설정하고 거리를 계산했다.

const input = `5 5
1 3
1 4
4 5
4 3
3 2`.split('\n').map(el => el.split(' ').map(Number))

const vertex = input[0][0]
const matrix = []
const result = []
for(let i = 0 ; i < vertex ; i++){
    matrix.push(new Array(vertex).fill(100))
    matrix[i][i] = 0
}

for(let i = 1 ; i < input.length ; i++){
    const [start, end] = input[i]
    matrix[start-1][end-1] = 1
    matrix[end-1][start-1] = 1
}

for(let i = 0 ; i < vertex ; i++){
    for(let j = 0 ; j < vertex ; j++){
        for(let k = 0 ; k < vertex ; k++){
            matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k])
        }
    }
}

for(let i = 0 ; i < vertex ; i++){
    let lowSum = 0
    for(let j = 0 ; j < vertex ; j++){
        lowSum += matrix[i][j]
    }
    result.push([lowSum, i+1])
}

console.log(result.sort((a,b) => a[0]-b[0])[0][1])