ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

[๋ฌธ์ œ]

https://school.programmers.co.kr/learn/courses/30/lessons/72413

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr

 

๋ฌธ์ œ ์„ค๋ช…

[๋ณธ ๋ฌธ์ œ๋Š” ์ •ํ™•์„ฑ๊ณผ ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ ๊ฐ๊ฐ ์ ์ˆ˜๊ฐ€ ์žˆ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.]

๋ฐค๋Šฆ๊ฒŒ ๊ท€๊ฐ€ํ•  ๋•Œ ์•ˆ์ „์„ ์œ„ํ•ด ํ•ญ์ƒ ํƒ์‹œ๋ฅผ ์ด์šฉํ•˜๋˜ ๋ฌด์ง€๋Š” ์ตœ๊ทผ ์•ผ๊ทผ์ด ์žฆ์•„์ ธ ํƒ์‹œ๋ฅผ ๋” ๋งŽ์ด ์ด์šฉํ•˜๊ฒŒ ๋˜์–ด ํƒ์‹œ๋น„๋ฅผ ์•„๋‚„ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์„ ๊ณ ๋ฏผํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. "๋ฌด์ง€"๋Š” ์ž์‹ ์ด ํƒ์‹œ๋ฅผ ์ด์šฉํ•  ๋•Œ ๋™๋ฃŒ์ธ ์–ดํ”ผ์น˜ ์—ญ์‹œ ์ž์‹ ๊ณผ ๋น„์Šทํ•œ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐ€๋Š” ํƒ์‹œ๋ฅผ ์ข…์ข… ์ด์šฉํ•˜๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. "๋ฌด์ง€"๋Š” "์–ดํ”ผ์น˜"์™€ ๊ท€๊ฐ€ ๋ฐฉํ–ฅ์ด ๋น„์Šทํ•˜์—ฌ ํƒ์‹œ ํ•ฉ์Šน์„ ์ ์ ˆํžˆ ์ด์šฉํ•˜๋ฉด ํƒ์‹œ์š”๊ธˆ์„ ์–ผ๋งˆ๋‚˜ ์•„๋‚„ ์ˆ˜ ์žˆ์„ ์ง€ ๊ณ„์‚ฐํ•ด ๋ณด๊ณ  "์–ดํ”ผ์น˜"์—๊ฒŒ ํ•ฉ์Šน์„ ์ œ์•ˆํ•ด ๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

์œ„ ์˜ˆ์‹œ ๊ทธ๋ฆผ์€ ํƒ์‹œ๊ฐ€ ์ด๋™ ๊ฐ€๋Šฅํ•œ ๋ฐ˜๊ฒฝ์— ์žˆ๋Š” 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;
}