문제
해결한 코드
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
var t = Number(input.shift())
var ways = Array(t)
var answer = ''
var floyd = []
var n = 0
if (t <= 1) {
n = input[0] / 1
var temp = []
for (var i = 1; i <= n + 2; i++) {
temp.push(input[i].split(' ').map((e) => e / 1))
}
ways[0] = temp
floyd = setFloyd(ways[0])
if (isPossible(floyd)) {
answer = 'happy'
} else {
answer = 'sad'
}
} else {
var index = 0
var waysIndex = 0
while (waysIndex !== t) {
n = input[index] / 1
var temp = []
for (var i = index + 1; i <= index + n + 2; i++) {
temp.push(input[i].split(' ').map((e) => e / 1))
}
ways[waysIndex] = temp
index = index + n + 2 + 1
waysIndex++
}
for (var idx = 0; idx < ways.length; idx++) {
floyd = setFloyd(ways[idx])
if (isPossible(floyd)) {
answer += 'happy' + '\n'
} else {
answer += 'sad' + '\n'
}
}
}
console.log(answer.trim())
function isPossible(floyd) {
var homeToFestival = floyd[0][floyd[0].length - 1]
if (homeToFestival === Infinity) return false
return true
}
function setFloyd(ways_index) {
var floyd = initFloyd(ways_index)
for (var i = 0; i < floyd.length; i++) {
for (var j = 0; j < floyd.length; j++) {
if (j === i) continue
for (var k = 0; k < floyd.length; k++) {
if (floyd[j][i] !== Infinity && floyd[i][k] !== Infinity && floyd[j][i] + floyd[i][k] < floyd[j][k]) {
floyd[j][k] = floyd[j][i] + floyd[i][k]
}
}
}
}
return floyd
}
function initFloyd(ways_index) {
var floyd = []
var current = ways_index
for (var i = 0; i < current.length; i++) {
floyd.push(Array(current.length).fill(Infinity))
floyd[i][i] = 0
}
for (var i = 0; i < current.length; i++) {
var now = current[i]
for (var j = 0; j < current.length; j++) {
if (j === i) continue
var value = Math.abs(current[j][0] - now[0]) + Math.abs(current[j][1] - now[1])
if (value <= 1000) {
floyd[i][j] = value
}
}
}
return floyd
}풀이
※ 플로이드 와샬 알고리즘을 사용한다.
1. 플로이드 그래프를 만든다.
원래 플로이드-와샬엔 정점간의 비용(가중치)이 주어지지만, 여기서는 주어지지 않았다.
다만, 두 정점간의 거리가 1000 이하여야 맥주를 마시면서 페스티벌에 갈 수 있다는 사실을 알 수 있다.
(왜냐하면 50미터에 한캔씩 마실 수 있고, 맥주는 최대 20캔을 가지고 있을 수 있기 때문)위 사실을 활용하여
- 두 정점간의 거리가 1000 이하면
- 1000을 넘으면
으로 나눠 가중치를 부여하였다.ex. 만약 다음과 같이 입력되었다면
testCase = 1 convenienceStoreNumber = 2 vertexs = [ [0, 0], <= 집 [1000, 0], <= 편의점 1 [1000, 1000], <= 편의점 2 [2000, 1000] <= 페스티벌 ]
자기 자신으로 향하는 거리는 0이니까, 일단 0을 넣었다.
- 집 -> 편의점 1
[1000, 0] - [0, 0] = [1000, 0]
상근이가 총 1000미터를 걸으면 편의점1에 갈 수 있다.
맥주 20캔 먹으면 편의점1에서 20캔 또 사먹을 수 있다.- 집 -> 편의점 2
[1000, 1000] - [0, 0] = [1000, 1000]
상근이가 1000 + 1000, 즉 총 2000미터를 걸어야 편의점2에 갈 수 있다.
맥주 20캔으론 모자라다..- 집 -> 페스티벌
[2000, 1000] - [0, 0] = [2000, 1000]
상근이가 2000 + 1000, 즉 총 3000미터를 걸어야 페스티벌에 갈 수 있다.
(역시) 맥주 20캔으론 모자라다..위에서 계산한 값에 따라 표를 채우면
집에서 편의점2, 페스티벌은 맥주 20캔으론 부족했다. 따라서 INF를 넣었다.다음으로 편의점1에서 집, 편의점2, 페스티벌을 맥주 20캔으로 갈 수 있는지 계산해보자.
- 편의점1 -> 집
[0, 0] - [1000, 0] = [-1000, 0]
거리니까 절댓값으로 계산하면 총 1000 미터가 된다.- 편의점1 -> 편의점 2
[1000, 1000] - [1000, 0] = [0, 1000]
총 1000미터가 된다.- 편의점 1 -> 페스티벌
[2000, 1000] - [1000, 0] = [1000, 1000]
총 2000미터가 된다.
맥주 20캔으로는 모자라다.위에서 계산한 값들로 다시 표를 채우면
이러한 방식으로
편의점2, 페스티벌도 같은 식으로 계산하여 표를 완성하면 다음과 같다.
위와 같이 플로이드 그래프를 완성하였다.2. 플로이드 와샬 알고리즘으로 계산한다.
만약 시작하는 정점이 s, 도착 정점이 d, 중간에 거치는 정점이 i라면,
s -> t의 거리 값은 다음과 같다.floydGraph[s][d] = min(floydGraph[s][d], floydGrapth[s][i] + floydGraph[i][d])여기서 문제에 맞게 응용을 해보면,
※ 현재 갈 수 없는 거리는 INF로 해놓았다.
다시말해, 맥주 20캔으로 갈 수 있는 거리는 INF가 아니다.👉🏻 따라서, s -> d는
floydGrapth[s][i] !== INFfloydGraph[i][d] !== INFfloydGrapth[s][i] + floydGraph[i][d] < floydGraph[s][d]이 모두 부합할 때 가능하다.
(참고로) 나는
floydGraph[s][d]의 값을floydGrapth[s][i] + floydGraph[i][d]로 하였다.거리를 계산한 플로이드 그래프를 완성하였다.
3. 집에서 페스티벌에 가는 값을 확인한다.
집에서 페스티벌 까지의 거리는 ?
플로이드 그래프에서 집의 페스티벌 값을 통해 알 수 있다.
- 만약 이 값이 INF라면? 집에서 페스티벌까지 가는데 맥주 흐름이 중간에 끊긴다는 뜻이다.
- INF가 아니라면? 집에서 페스티벌 까지 가는데 맥주 흐름 안끊기고 갈 수 있다는 의미다.
4. 3번 확인여부에 따라 happy || sad 를 출력한다.
그래프 관련것들.. 나에겐 넘 어렵다.. 후..
