[코딩테스트]백준 - 파티(1238)

문제

파티(1238)

해결한 코드

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
var informations = input[0].split(' ')
var n = +informations[0]
var m = +informations[1]
var x = +informations[2]
var answer = 0
if (n === 1) {
    console.log(answer)
} else {
    var mapInformations = []
    for (var i = 1; i < input.length; i++) {
        mapInformations.push(input[i].split(' ').map((e) => +e))
    }
    var floyd = setFloyd()
    answer = findMaxtimeOfRoundTrip(floyd)
    console.log(answer)

    function findMaxtimeOfRoundTrip(floyd) {
        var timeFromDestination = floyd[x - 1]
        var max = 0
        for (var i = 0; i < floyd.length; i++) {
            var oneWayToDestination = floyd[i][x - 1]
            timeFromDestination[i] += oneWayToDestination
            if (max < timeFromDestination[i]) {
                max = timeFromDestination[i]
            }
        }
        return max
    }

    function setFloyd() {
        var floyd = initFloyd()
        for (var i = 0; i < n; i++) {
            for (var j = 0; j < n; j++) {
                if (j === i) continue
                for (var k = 0; k < n; k++) {
                    if (floyd[j][i] !== Infinity && floyd[i][k] !== Infinity && floyd[j][k] > floyd[j][i] + floyd[i][k]) {
                        floyd[j][k] = floyd[j][i] + floyd[i][k]
                    }
                }
            }
        }
        return floyd
    }

    function initFloyd() {
        var floyd = []
        for (var i = 0; i < n; i++) {
            floyd.push(Array(n).fill(Infinity))
            floyd[i][i] = 0
        }
        for (var i = 0; i < mapInformations.length; i++) {
            var s = mapInformations[i][0]
            var d = mapInformations[i][1]
            var w = mapInformations[i][2]
            floyd[s - 1][d - 1] = w
        }
        return floyd
    }
}

풀이

※ 플로이드 와샬 알고리즘으로 풀었다.

1. 플로이드 그래프를 만든다.

n = 4, m = 8, x = 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 ]
]

그림으로 다음과 같이 나타낼 수 있다.

자기 자신에 대한 거리의 비용은 0으로,
입력으로 받은 도로 정보는 직결된 도로라는 의미이므로, 입력된 비용을 넣는다.

🖐🏻 나머지 도로는?
직결되지 않았으므로 현재 어떻게 가야하는지 모르니 INF 값을 주도록 한다.

초기 플로이드 그래프를 완성하였다.

2. 플로이드 와샬 알고리즘으로 도로 비용을 계산한다.

시작하는 점을 s, 도착하는 점을 d, 중간에 거치는 지점을 i라고 하면,

floyd[s][d] = min(floyd[s][i] + floyd[i][d], floyd[s][d])

이므로, 이에 따라 도로의 비용을 계산한다.

📌 도로의 비용을 계산할 때는
✔ s와 i는 연결된 도로인지
✔ i를 거쳐 d로 가는 것이 더 적은 비용이 드는지
를 염두하여 계산한다.

i가 1일 때부터 4일 때까지 각 지점들을 계산하면 다음과 같은 모양으로 플로이드 그래프가 수정된다.

3. x마을로의 왕복 비용을 계산한다.

2번 마을로부터 각 마을로 돌아가는데 걸리는 비용은

바로 2번 행의 값을 통해 알 수 있다.
그럼 이 비용에서 2번 마을로 가는데 걸리는 비용을 더해주면 왕복 비용이 된다.

각 마을에서 2번 마을로 가는 비용을 더한다.
👉🏻 [1, 0, 3, 7] + [4, 0, 6, 3] = [5, 0, 9, 10]

왕복 비용이 모두 계산되었다.

3. 왕복 비용의 최댓값을 출력한다.

가만보니 다익스트라 알고리즘으로도 풀 수 있을 것 같다.
현재 플로이드와샬 연습중이라 플로이드로 풀었는데 시간도 많이 걸리고... 조만간 다익스트라 공부하고 접근해봐야지 !