[개발일지] - 404(주말)

(1).백준 2660번 회장 뽑기는 가장 사람들과 많이 아는 사람을 회장으로 뽑아야 하는 문제였다.

 

각 관계는 플로이드 워셜을 통해서 빠르게 해결할 수 있었는데

이번에는 ㅍ한번도 이전에 푼 문제를 참조하지 않고 바로 플로이드-워셜을 적용할 수 있었다.

 

나온 결과문에서 각각의 사람마다 가장 먼 관계를 Math.max와 구조분해 할당을 통해 구해줬고

그 중 가장 작은 값을 다시 Math.min과 구조분해할당으로 구한 다음

해당 값을 가진 사람들을 배열에 담아서 숫자와 각각의 사람 index를 출력해서 문제를 해결할 수 있었다.

const input = `5
1 2
2 3
3 4
4 5
2 4
5 3
-1 -1`.split('\n')

const vertex = Number(input[0])
const map = []
const point = []

for(let i = 0 ; i < vertex ; i++){
    map.push(new Array(vertex).fill(50))
    map[i][i] = 1
}

for(let i = 1 ; i < input.length - 1 ; i++){
    const [start, end] = input[i].split(' ').map(Number)
    map[start-1][end-1] = 1
    map[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++){
            map[j][k] = Math.min(map[j][k], map[j][i] + map[i][k])
        }
    }
}

for(let i = 0 ; i < vertex ; i++){
    point.push(Math.max(...map[i]))
}

const results = []
const limit = Math.min(...point)

for(let i = 0 ; i < vertex ; i++){
    if(point[i] == limit){
        results.push(i+1)
    }
}

console.log(limit, results.length)
console.log(...results)