ํฐ์คํ ๋ฆฌ ๋ทฐ
[JavaScript] ํ๋ก๊ทธ๋๋จธ์ค - ํฉ์น ํ์ ์๊ธ
๊ฐ๋ฐ๊ฐ๊ตด๐ธ 2022. 8. 27. 21:00[๋ฌธ์ ]
https://school.programmers.co.kr/learn/courses/30/lessons/72413
๋ฌธ์ ์ค๋ช
[๋ณธ ๋ฌธ์ ๋ ์ ํ์ฑ๊ณผ ํจ์จ์ฑ ํ ์คํธ ๊ฐ๊ฐ ์ ์๊ฐ ์๋ ๋ฌธ์ ์ ๋๋ค.]
๋ฐค๋ฆ๊ฒ ๊ท๊ฐํ ๋ ์์ ์ ์ํด ํญ์ ํ์๋ฅผ ์ด์ฉํ๋ ๋ฌด์ง๋ ์ต๊ทผ ์ผ๊ทผ์ด ์ฆ์์ ธ ํ์๋ฅผ ๋ ๋ง์ด ์ด์ฉํ๊ฒ ๋์ด ํ์๋น๋ฅผ ์๋ ์ ์๋ ๋ฐฉ๋ฒ์ ๊ณ ๋ฏผํ๊ณ ์์ต๋๋ค. "๋ฌด์ง"๋ ์์ ์ด ํ์๋ฅผ ์ด์ฉํ ๋ ๋๋ฃ์ธ ์ดํผ์น ์ญ์ ์์ ๊ณผ ๋น์ทํ ๋ฐฉํฅ์ผ๋ก ๊ฐ๋ ํ์๋ฅผ ์ข ์ข ์ด์ฉํ๋ ๊ฒ์ ์๊ฒ ๋์์ต๋๋ค. "๋ฌด์ง"๋ "์ดํผ์น"์ ๊ท๊ฐ ๋ฐฉํฅ์ด ๋น์ทํ์ฌ ํ์ ํฉ์น์ ์ ์ ํ ์ด์ฉํ๋ฉด ํ์์๊ธ์ ์ผ๋ง๋ ์๋ ์ ์์ ์ง ๊ณ์ฐํด ๋ณด๊ณ "์ดํผ์น"์๊ฒ ํฉ์น์ ์ ์ํด ๋ณด๋ ค๊ณ ํฉ๋๋ค.
์ ์์ ๊ทธ๋ฆผ์ ํ์๊ฐ ์ด๋ ๊ฐ๋ฅํ ๋ฐ๊ฒฝ์ ์๋ 6๊ฐ ์ง์ ์ฌ์ด์ ์ด๋ ๊ฐ๋ฅํ ํ์๋
ธ์ ๊ณผ ์์์๊ธ์ ๋ณด์ฌ์ฃผ๊ณ ์์ต๋๋ค.
๊ทธ๋ฆผ์์ A์ B ๋ ์ฌ๋์ ์ถ๋ฐ์ง์ ์ธ 4๋ฒ ์ง์ ์์ ์ถ๋ฐํด์ ํ์๋ฅผ ํ๊ณ ๊ท๊ฐํ๋ ค๊ณ ํฉ๋๋ค. A์ ์ง์ 6๋ฒ ์ง์ ์ ์์ผ๋ฉฐ B์ ์ง์ 2๋ฒ ์ง์ ์ ์๊ณ ๋ ์ฌ๋์ด ๋ชจ๋ ๊ท๊ฐํ๋ ๋ฐ ์์๋๋ ์์ ์ต์ ํ์์๊ธ์ด ์ผ๋ง์ธ ์ง ๊ณ์ฐํ๋ ค๊ณ ํฉ๋๋ค.
- ๊ทธ๋ฆผ์ ์์ ์ง์ ์ ๋ํ๋ด๋ฉฐ ์ ์์ ์ซ์๋ ์ง์ ๋ฒํธ๋ฅผ ๋ํ๋
๋๋ค.
- ์ง์ ์ด n๊ฐ์ผ ๋, ์ง์ ๋ฒํธ๋ 1๋ถํฐ n๊น์ง ์ฌ์ฉ๋ฉ๋๋ค.
- ์ง์ ๊ฐ์ ํ์๊ฐ ์ด๋ํ ์ ์๋ ๊ฒฝ๋ก๋ฅผ ๊ฐ์ ์ด๋ผ ํ๋ฉฐ, ๊ฐ์ ์ ํ์๋ ์ซ์๋ ๋ ์ง์ ์ฌ์ด์ ์์ ํ์์๊ธ์ ๋ํ๋
๋๋ค.
- ๊ฐ์ ์ ํธ์ ์ ์ง์ ์ผ๋ก ํ์๋์ด ์์ต๋๋ค.
- ์ ๊ทธ๋ฆผ ์์์์, 4๋ฒ ์ง์ ์์ 1๋ฒ ์ง์ ์ผ๋ก(4→1) ๊ฐ๊ฑฐ๋, 1๋ฒ ์ง์ ์์ 4๋ฒ ์ง์ ์ผ๋ก(1→4) ๊ฐ ๋ ์์ ํ์์๊ธ์ 10์์ผ๋ก ๋์ผํ๋ฉฐ ์ด๋ ๋ฐฉํฅ์ ๋ฐ๋ผ ๋ฌ๋ผ์ง์ง ์์ต๋๋ค.
- ์์๋๋ ์ต์ ํ์์๊ธ์ ๋ค์๊ณผ ๊ฐ์ด ๊ณ์ฐ๋ฉ๋๋ค.
- 4→1→5 : A, B๊ฐ ํฉ์นํ์ฌ ํ์๋ฅผ ์ด์ฉํฉ๋๋ค. ์์ ํ์์๊ธ์ 10 + 24 = 34์ ์ ๋๋ค.
- 5→6 : A๊ฐ ํผ์ ํ์๋ฅผ ์ด์ฉํฉ๋๋ค. ์์ ํ์์๊ธ์ 2์ ์ ๋๋ค.
- 5→3→2 : B๊ฐ ํผ์ ํ์๋ฅผ ์ด์ฉํฉ๋๋ค. ์์ ํ์์๊ธ์ 24 + 22 = 46์ ์ ๋๋ค.
- A, B ๋ชจ๋ ๊ท๊ฐ ์๋ฃ๊น์ง ์์๋๋ ์ต์ ํ์์๊ธ์ 34 + 2 + 46 = 82์ ์ ๋๋ค.
๋ฌธ์
์ง์ ์ ๊ฐ์ n, ์ถ๋ฐ์ง์ ์ ๋ํ๋ด๋ s, A์ ๋์ฐฉ์ง์ ์ ๋ํ๋ด๋ a, B์ ๋์ฐฉ์ง์ ์ ๋ํ๋ด๋ b, ์ง์ ์ฌ์ด์ ์์ ํ์์๊ธ์ ๋ํ๋ด๋ fares๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. ์ด๋, A, B ๋ ์ฌ๋์ด s์์ ์ถ๋ฐํด์ ๊ฐ๊ฐ์ ๋์ฐฉ ์ง์ ๊น์ง ํ์๋ฅผ ํ๊ณ ๊ฐ๋ค๊ณ ๊ฐ์ ํ ๋, ์ต์ ์์ ํ์์๊ธ์ ๊ณ์ฐํด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์.
๋ง์ฝ, ์์ ํฉ์น์ ํ์ง ์๊ณ ๊ฐ์ ์ด๋ํ๋ ๊ฒฝ์ฐ์ ์์ ํ์์๊ธ์ด ๋ ๋ฎ๋ค๋ฉด, ํฉ์น์ ํ์ง ์์๋ ๋ฉ๋๋ค.
์ ํ์ฌํญ
- ์ง์ ๊ฐฏ์ n์ 3 ์ด์ 200 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
- ์ง์ s, a, b๋ 1 ์ด์ n ์ดํ์ธ ์์ฐ์์ด๋ฉฐ, ๊ฐ๊ธฐ ์๋ก ๋ค๋ฅธ ๊ฐ์
๋๋ค.
- ์ฆ, ์ถ๋ฐ์ง์ , A์ ๋์ฐฉ์ง์ , B์ ๋์ฐฉ์ง์ ์ ์๋ก ๊ฒน์น์ง ์์ต๋๋ค.
- fares๋ 2์ฐจ์ ์ ์ ๋ฐฐ์ด์ ๋๋ค.
- fares ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 2 ์ด์ n x (n-1) / 2 ์ดํ์
๋๋ค.
- ์๋ฅผ๋ค์ด, n = 6์ด๋ผ๋ฉด fares ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 2 ์ด์ 15 ์ดํ์ ๋๋ค. (6 x 5 / 2 = 15)
- fares ๋ฐฐ์ด์ ๊ฐ ํ์ [c, d, f] ํํ์ ๋๋ค.
- c์ง์ ๊ณผ d์ง์ ์ฌ์ด์ ์์ ํ์์๊ธ์ด f์์ด๋ผ๋ ๋ป์ ๋๋ค.
- ์ง์ c, d๋ 1 ์ด์ n ์ดํ์ธ ์์ฐ์์ด๋ฉฐ, ๊ฐ๊ธฐ ์๋ก ๋ค๋ฅธ ๊ฐ์ ๋๋ค.
- ์๊ธ f๋ 1 ์ด์ 100,000 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
- fares ๋ฐฐ์ด์ ๋ ์ง์ ๊ฐ ์์ ํ์์๊ธ์ 1๊ฐ๋ง ์ฃผ์ด์ง๋๋ค. ์ฆ, [c, d, f]๊ฐ ์๋ค๋ฉด [d, c, f]๋ ์ฃผ์ด์ง์ง ์์ต๋๋ค.
- ์ถ๋ฐ์ง์ s์์ ๋์ฐฉ์ง์ a์ b๋ก ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์กด์ฌํ๋ ๊ฒฝ์ฐ๋ง ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋๋ค.
[ํ์ด]
๋ฌด์ง์ ์ดํผ์น๊ฐ S์์ ํ์นํด์ ์ด๋ํ ๋ ธ๋๊น์ง์ ์ต์๊ฑฐ๋ฆฌ์์ ํด๋น ๋ ธ๋๋ถํฐ A, B๊น์ง์ ๊ฐ๊ฐ์ ๊ฑฐ๋ฆฌ๋ฅผ ๋ํ ํฉ์ด ์ต์๊ฐ ๋๋ ๋ ธ๋๊น์ง ํฉ์นํ๋ฉด ์ต์ ์๊ฐ์ ๊ตฌํ ์ ์์ต๋๋ค.
์ฐ์ , ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด ์ ์ S, A, B์์ ๋ชจ๋ ๋ ธ๋์ ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ์ ์ ์ฅํด์ผํฉ๋๋ค.
์์์ node๋ถํฐ ๋ชจ๋ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ค์ต์คํธ๋ผ๋ ๋ค์๊ณผ ๊ฐ์ด ์๋ํฉ๋๋ค.
์ด๊ธฐ ์ธํ
- ํฌ๊ธฐ๊ฐ n+1์ธ dist๋ฐฐ์ด์ -1๋ก ์ด๊ธฐํ. ( -1์ ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ง์ ์ ๋ปํจ)
- ์์์ node์์ node๊น์ง์ ๊ฑฐ๋ฆฌ๋ 0์ด๋ฏ๋ก dist[node] = 0
- queue์ node๋ฅผ ๋ฃ๊ณ ํ์์ ์์
ํ์ ๊ณผ์
1. queue๊ฐ ๋น์ด์์ง ์๋ค๋ฉด(๋ฐฉ๋ฌธํด์ผํ ๋ ธ๋๊ฐ ๋จ์ ์๋ค๋ฉด) queue์์ shift์ฐ์ฐ์ ํตํด node๋ฅผ ๋ฝ์๋ ๋๋ค.
2. node์ ์ฐ๊ฒฐ๋ ์ ์ ๋ค์ ํ์ํ๋ฉฐ ์๋์ ๊ฐ์ด ๊ฐ์ ๊ฐฑ์ ํฉ๋๋ค.
- dist[node] === -1 (์์ง ํ๋ฒ๋ ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋)๋ผ๋ฉด dist๊ฐ์ ํ์ฌ node๊น์ง์ ๊ฑฐ๋ฆฌ + node์ ์ ์ ์ ๊ฑฐ๋ฆฌ๋ก ๊ฐฑ์
- dist[node] !== -1 (์ด์ ์ ๋ฐฉ๋ฌธํ๋ ๋ ธ๋)๋ผ๋ฉด dist[node]๊ฐ์ด ํ์ฌ node๊น์ง์ ๊ฑฐ๋ฆฌ + node์ ์ ์ ์ ๊ฑฐ๋ฆฌ๋ณด๋ค ํฌ๋ฉด ๊ฐฑ์
3. ๊ฐฑ์ ๋ ์ ์ ๋ค์ queue์ push์ฐ์ฐ์ ํตํด ์ถ๊ฐํฉ๋๋ค.
๋ค์ต์คํธ๋ผ๋ฅผ ํ์ฉํด S, A, B์ ๋ํด ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ฉด ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- S์ ๋ชจ๋ ์ ์ ๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ ๋ฐฐ์ด distS : [-1, 10, 66, 51, 0, 34, 35]
- A์ ๋ชจ๋ ์ ์ ๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ ๋ฐฐ์ด distA : [-1, 25, 48, 26, 35, 2, 0]
- B์ ๋ชจ๋ ์ ์ ๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ ๋ฐฐ์ด distB : [-1, 63, 0, 22, 66, 46, 48]
์ต์ ์๊ฐ = (S์์ ํฉ์นํด์ ์ด๋ํ ๋ ธ๋๊น์ง์ ๊ฑฐ๋ฆฌ + ์ด๋ํ ๋ ธ๋์์ A๊น์ง์ ๊ฑฐ๋ฆฌ + ์ด๋ํ ๋ ธ๋์์ B๊น์ง์ ๊ฑฐ๋ฆฌ)์ด๋ฏ๋ก for๋ฌธ์ ํตํด distS, distA, distB๋ฅผ ํ์ํ๋ฉฐ ๊ฑฐ๋ฆฌ์ ํฉ์ด ์ต์์ธ ๊ฐ์ ๊ฐฑ์ ํฉ๋๋ค.
(๋จ, distS์ ๊ฐ์ด -1์ธ ๊ฒฝ์ฐ ์ ๊ทผ ๋ถ๊ฐ๋ฅํ ๋ ธ๋์ด๊ธฐ ๋๋ฌธ์ -1์ด ์๋ ๋ ธ๋๋ง ๊ฒ์ฌํฉ๋๋ค.)
๋ฐ๋ผ์ ์ต์ ์๊ฐ์ 5๊น์ง ํฉ์นํ ๊ฑฐ๋ฆฌ + 5์ A์ ๊ฑฐ๋ฆฌ + 5์ B์ ๊ฑฐ๋ฆฌ = 34 + 2 + 46 = 82 ์ ๋๋ค.
[์ฝ๋]
function solution(n, s, a, b, fares) {
var answer = Number.MAX_VALUE;
// ๊ฐ์ ์ฐ๊ฒฐ ์ ๋ณด ์ ์ฅ
const graph = Array.from({length: n+1}, () => []);
fares.forEach((fare) => {
const [s, e, d] = fare;
graph[s].push([e, d]);
graph[e].push([s, d]);
})
// node ๋ถํฐ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํจ
const dijkstra = (node) => {
const dist = Array.from({length: n+1}, () => Number.MAX_VALUE);
const queue = [];
queue.push(node);
dist[node] = 0;
while(queue.length !== 0) {
const p = queue.shift();
graph[p].forEach((item) => {
const [e, d] = item;
if(dist[e] > dist[p] + d) {
dist[e] = dist[p] + d;
queue.push(e);
}
})
}
return dist;
}
// S, A, B ๊ฐ๊ฐ์ ๋ชจ๋ ๋
ธ๋์์ ๊ฑฐ๋ฆฌ
const distS = dijkstra(s);
const distA = dijkstra(a);
const distB = dijkstra(b);
for(let i=1;i<=n;i++) {
// ์ ๊ทผํ ์ ์๋ ์ ์ ์ pass
if(distS[i] === Number.MAX_VALUE) {
continue;
}
answer = Math.min(answer, distS[i] + distA[i] + distB[i]);
}
return answer;
}
'Algorithm > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[JavaScript] ํ๋ก๊ทธ๋๋จธ์ค - ์ฑ๊ฒฉ ์ ํ ๊ฒ์ฌํ๊ธฐ (0) | 2022.09.01 |
---|---|
[JavaScript] ํ๋ก๊ทธ๋๋จธ์ค - ์นด๋ ์ง ๋ง์ถ๊ธฐ (0) | 2022.08.31 |
[JavaScript] ํ๋ก๊ทธ๋๋จธ์ค - ์ ๊ตญ์ฌ์ฌ (0) | 2022.08.27 |
[JavaScript] ํ๋ก๊ทธ๋๋จธ์ค - ์์ฅ (0) | 2022.08.26 |
[JavaScript] ํ๋ก๊ทธ๋๋จธ์ค - ๊ฐ์ฅ ๋จผ ๋ ธ๋ (0) | 2022.08.26 |
- Total
- Today
- Yesterday
- Baekjoon
- ๋์์ธ ํจํด
- ๋ฐฑ์ค javascript
- 2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด
- ์๋ฐ์คํฌ๋ฆฝํธ
- ์ด์์ฒด์
- ํ๋กํ ์ฝ
- map
- ์นด์นด์ค ์ธํด
- ์ด๋ถํ์
- http
- JavaScript
- ํจ์ํ ํ๋ก๊ทธ๋๋ฐ
- ๋คํธ์ํฌ
- git
- ๋ฐฑ์ค node.js
- ๊ฐ์ฒด์งํฅ ํ๋ก๊ทธ๋๋ฐ
- ํ๋กํผํฐ
- ์๊ณ ๋ฆฌ์ฆ
- TDD
- ๋ชจ๋ ์๋ฐ์คํฌ๋ฆฝํธ deep dive
- ํฌํฌ์ธํฐ
- ์ฝ๋ฉํ ์คํธ
- ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
- ์ ์ญ ๋ณ์
- fp
- ์๋ฐ
- ๋ฐฑ์ค
- ๋ ์์ปฌ ํ๊ฒฝ
- ํ๋ก๊ทธ๋๋จธ์ค
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |