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

(1).백준 1238번 파티는 파티에 참가하는 학생들의 주소값들이 정해져있고

각각 이동할 수 있는 경로가 따로 있다고 할 때 파티 참여 후 복귀 시간이 가장 오래 걸리는 시간을 구해야 하는 문제였다.

 

아래에 추천 태그는 다익스트라지만 사실상 전체 인원을 다 파악해야 하기 때문에 플로이드 워셜이 더 좋아보였고

그냥  플로이드 워셜로 풀고 제출하니 정상적으로 통과했다.

 

플로이드 워셜의 경우에는 a -> b로 가는 최적의 경로는

a -> x -> b와 a -> b의 모든 경우의 수 중 가장 짧은 거리라 3중 for문으로 순회하는 방식으로 진행되며

단방향 경로라 시작할 때 각각 map에 값을 담아줬고

map이라는 배열을 생성할 때는 예전에는 for문을 순회하며 작성했지만 forEach를 써보고 싶었는데

배열 생성 후 진행되는 부분이라 그냥 map으로 처리해도 참조값 복사가 아니라 각각 할당되는 것을 확인하고 map()을 싸용했다.

 

중간에 본인 위치는 0이라는 내용을 기입하지 않고 Infinity로 마무리해서 한번 오답이 나왔는데

경로값을 넣어줄 때 본인 위치는 0이라는 당연한 내용을 까먹지 않고 기입하도록 주의해야겠다.

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

const [student, load, partyPlace] = input.shift()
const map = new Array(student).fill().map(() => new Array(student).fill(Infinity))
let maxTime = 0



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

for(let i = 0 ; i < student ; i++){
    map[i][i] = 0
}

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

for(let i = 0 ; i < student ; i++){
    maxTime = Math.max(maxTime, map[i][partyPlace-1] + map[partyPlace-1][i])
}

console.log(maxTime)