โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Shortest Path

[์ตœ๋‹จ ๊ฒฝ๋กœ] [Python] 10217. KCM Travel - GOLD โ… 

2021. 4. 17. 19:57
๋ชฉ์ฐจ
  1. ์ž…๋ ฅ
  2. ์ถœ๋ ฅ
  3. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•

๋ณธ ๊ฒŒ์‹œ๊ธ€์€ PC๋ฒ„์ „์— ์ตœ์ ํ™” ๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค.

 

 

10217๋ฒˆ: KCM Travel

๊ฐ๊ณ ์˜ ๋…ธ๋ ฅ ๋์— ์ฐฌ๋ฏผ์ด๋Š” 2014 Google Code Jam World Finals์— ์ง„์ถœํ•˜๊ฒŒ ๋˜์—ˆ๋‹ค. ๊ตฌ๊ธ€์—์„œ ์˜จ ์ดˆ๋Œ€์žฅ์„ ๋ฐ›๊ณ  ๊ธฐ๋ปํ–ˆ๋˜ ๊ฒƒ๋„ ์ž ์‹œ, ์ฐฌ์ฐฌํžˆ ์ฝ์–ด๋ณด๋˜ ์ฐฌ๋ฏผ์ด๋Š” ์ค‘์š”ํ•œ ์‚ฌ์‹ค์„ ์•Œ์•„์ฐจ๋ ธ๋‹ค. ์ตœ๊ทผ์˜ ๋Œ€์„ธ

www.acmicpc.net

 

์ž…๋ ฅ

์ž…๋ ฅ ํŒŒ์ผ์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ˆ˜๋ฅผ ์˜๋ฏธํ•˜๋Š” ์ž์—ฐ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ์—๋Š” T๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ ์ค„์—๋Š” ๊ณตํ•ญ์˜ ์ˆ˜ N (2 โ‰ค N โ‰ค 100), ์ด ์ง€์›๋น„์šฉ M (0 โ‰ค M โ‰ค 10,000), ํ‹ฐ์ผ“์ •๋ณด์˜ ์ˆ˜ K (0 โ‰ค K โ‰ค 10,000)๊ฐ€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. ์ด์–ด์„œ K๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ ํ‹ฐ์ผ“์˜ ์ถœ๋ฐœ๊ณตํ•ญ u, ๋„์ฐฉ๊ณตํ•ญ v (1 โ‰ค u, v โ‰ค N, u โ‰  v), ๋น„์šฉ c (1 โ‰ค c โ‰ค M, ์ •์ˆ˜), ๊ทธ๋ฆฌ๊ณ  ์†Œ์š”์‹œ๊ฐ„ d (1 โ‰ค d โ‰ค 1,000) ๊ฐ€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. ์ธ์ฒœ์€ ์–ธ์ œ๋‚˜ 1๋ฒˆ ๋„์‹œ์ด๊ณ , LA๋Š” ์–ธ์ œ๋‚˜ N๋ฒˆ ๋„์‹œ์ด๋‹ค

์ถœ๋ ฅ

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋‹น ํ•œ ์ค„์— ์ฐฌ๋ฏผ์ด LA์— ๋„์ฐฉํ•˜๋Š” ๋ฐ ๊ฑธ๋ฆฌ๋Š” ๊ฐ€์žฅ ์งง์€ ์†Œ์š”์‹œ๊ฐ„์„ ์ถœ๋ ฅํ•œ๋‹ค.

๋งŒ์•ฝ, LA์— ๋„์ฐฉํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ "Poor KCM"์„ ์ถœ๋ ฅํ•œ๋‹ค.


ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•

์ด ๋ฌธ์ œ๋ฅผ ์ฒ˜์Œ ์ ‘ํ–ˆ์„ ๋•Œ๋Š” ์†Œ์š” ์‹œ๊ฐ„์„ ์šฐ์„ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋˜ ๋น„์šฉ๊นŒ์ง€ ๊ณ ๋ คํ•ด์•ผํ•˜๋Š” ๋ฌธ์ œ๋ผ๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค.

์†Œ์š” ์‹œ๊ฐ„์ด ์งง์€ ์ˆœ์œผ๋กœ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•˜๋ฉด์„œ ์ตœ๋‹จ ๊ฒฝ๋กœ์˜ ๋น„์šฉ์ด ์ด ์ง€์› ๋น„์šฉ์„ ์ดˆ๊ณผํ•ด๋ฒ„๋ฆฌ๋Š” ๊ฒฝ์šฐ์—

Poor KCM์„ ์ถœ๋ ฅํ•˜๋ฉด ๋˜๋Š” ๊ฐ„๋‹จํ•œ(?) ๋ฌธ์ œ๋ผ๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค.

 

๊ทธ๋ ‡๊ฒŒ ๊ตฌํ˜„์„ ํ•˜๊ณ  ์‹คํ–‰์„ ๋Œ๋ ธ๋Š”๋ฐ?

 

ํ—ˆํ—ˆ...

 

์ด ๋ฌธ์ œ๋Š” ๊ตฌ๊ธ€๋ง์„ ํ†ตํ•ด ํ•ด๊ฒฐํ•œ ๋ฌธ์ œ์ด๋‹ค...ใ… 

 

์ด ๋ฌธ์ œ์—์„œ ์ค‘์š”ํ•œ ์ ์€ ์†Œ์š” ์‹œ๊ฐ„์€ ์งง์ง€๋งŒ ๋น„์šฉ์ด ๋น„์‹ผ ๊ฒฝ์šฐ, ์†Œ์š” ์‹œ๊ฐ„์€ ๊ธธ์ง€๋งŒ ๋น„์šฉ์ด ์‹ผ ๊ฒฝ์šฐ ์œ„์˜ ๋‘ ๊ฒฝ์šฐ๋ฅผ ๋ชจ๋‘ ํƒ์ƒ‰ํ•ด์•ผํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ๋‹จ์ˆœํžˆ ์†Œ์š” ์‹œ๊ฐ„์œผ๋กœ ๋‹ค์ต์ŠคํŠธ๋ผ๋ฅผ ๋Œ๋ฆฌ๊ฒŒ ๋˜๋ฉด ๋‹น์—ฐํžˆ ์†Œ์š” ์‹œ๊ฐ„์ด ์งง์€ ๊ฒฝ๋กœ๋กœ ๋‹ค์ต์ŠคํŠธ๋ผ๊ฐ€ ์ง„ํ–‰๋˜๊ณ  ์šฐ๋ฆฌ๊ฐ€ ์›ํ•˜๋Š” ๊ฒฐ๊ณผ๋ฅผ ์–ป์„ ์ˆ˜ ์—†๊ฒŒ ๋  ์ˆ˜๋„ ์žˆ๋‹ค. (๊ทธ๋ž˜์„œ ํ‹€๋ฆฌ๊ธฐ๋„ ํ–ˆ๊ณ ...) ์•„๋ฌดํŠผ ๊ตฌ๊ธ€๋ง์„ ํ†ตํ•ด ์–ป์€ ๊ฒƒ์€ DP๋ฅผ ํ†ตํ•ด ํ•ด๊ฒฐํ•˜๊ณ  ์žˆ์—ˆ๋‹ค.

 

์šฐ์„  ๋‚ด๊ฐ€ ์ฒ˜์Œ์œผ๋กœ ๊ตฌํ˜„ํ•œ ์ฝ”๋“œ์ด๋‹ค.

 

์ผ๋ฐ˜์ ์ธ ๋‹ค์ต์ŠคํŠธ๋ผ์— ํ•œ ๊ฐ€์ง€ ๊ฐ€์ค‘์น˜(๋น„์šฉ)์„ ์ถ”๊ฐ€ํ•˜์—ฌ ์ตœ๋‹จ ์†Œ์š” ์‹œ๊ฐ„ ๊ฒฝ๋กœ๋กœ ์ง„ํ–‰ํ–ˆ์„ ๊ฒฝ์šฐ์˜ ๋น„์šฉ์„ ์ €์žฅํ•˜๋„๋ก ๊ตฌํ˜„ํ–ˆ๋‹ค.

์ฃผ์–ด์ง„ ์ž…๋ ฅ ๊ฐ’์—์„œ๋Š” ๋ฌธ์ œ๊ฐ€ ์—†์—ˆ๋‹ค. ํ•˜์ง€๋งŒ ์—ญ์‹œ ๋ฐ˜๋ก€. 

 

๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ƒํ™ฉ์„ ๊ณ ๋ คํ•ด๋ณด์ž.

์œ„์—์„œ ์–ธ๊ธ‰ํ–ˆ๋˜ ๊ฒƒ์ฒ˜๋Ÿผ ๋‚ด๊ฐ€ ๊ตฌํ˜„ํ•œ ๋‹ค์ต์ŠคํŠธ๋ผ๋Š” ์†Œ์š”์‹œ๊ฐ„์„ ๊ธฐ์ค€์œผ๋กœ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ํƒ์ƒ‰ํ•˜๋ฏ€๋กœ

1. ์†Œ์š” ์‹œ๊ฐ„์€ ์งง์ง€๋งŒ ๋น„์šฉ์ด ๋น„์‹ผ ๊ฒฝ์šฐ

2. ์†Œ์š” ์‹œ๊ฐ„์€ ๊ธธ์ง€๋งŒ ๋น„์šฉ์ด ์‹ผ ๊ฒฝ์šฐ

๋‹น์—ฐํžˆ 1๋ฒˆ ๊ฒฝ๋กœ๋กœ ์ง„ํ–‰ํ•˜๊ฒŒ ๋œ๋‹ค. ํ•˜์ง€๋งŒ 1๋ฒˆ ๊ฒฝ๋กœ์˜ ๋น„์šฉ์ด ์ด ์ง€์›๋น„์šฉ์„ ์ดˆ๊ณผํ•˜๊ฒŒ ๋˜๋ฉด Poor KCM์ด ์ถœ๋ ฅ๋  ๊ฒƒ์ด๋‹ค.

2๋ฒˆ ๊ฒฝ๋กœ๊ฐ€ ๋น„๋ก 1๋ฒˆ ๊ฒฝ๋กœ๋ณด๋‹ค๋Š” ์†Œ์š” ์‹œ๊ฐ„์€ ์งง์ง€๋งŒ ๋น„์šฉ์ด ์ด ์ง€์›๋น„์šฉ ์ด๋‚ด๋กœ ๋“ค์–ด์˜ฌ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— 2๋ฒˆ ๊ฒฝ๋กœ๋กœ๋Š” ์ง„ํ–‰์ด ๊ฐ€๋Šฅํ• ์ˆ˜๋„ ์žˆ๋Š”๋ฐ ๋ง์ด๋‹ค. ๊ฒฐ๊ณผ์ ์œผ๋กœ ๋กœ์ง ์ž์ฒด๊ฐ€ ๋ฌธ์ œ๊ฐ€ ์žˆ์—ˆ๊ณ  ๊ฐˆ์•„์—Ž์–ด์•ผํ–ˆ๋‹ค.

 

๊ตฌ๊ธ€๋ง์„ ํ†ตํ•ด ์–ป์€ ์ฝ”๋“œ๋Š” DP๋ฅผ ํ†ตํ•ด ํ•ด๊ฒฐํ•˜๊ณ  ์žˆ์—ˆ๋‹ค.

"์ฃผ์–ด์ง„ ์ •์  X ์ด ์ง€์›๋น„์šฉ" ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•˜๊ณ  INF๋กœ ์ดˆ๊ธฐํ™” ํ•ด์คฌ๋‹ค.

ํ•œ๋งˆ๋””๋กœ ๋ชจ๋“  ์ •์ ์— ๋Œ€ํ•ด ์ด ์ง€์›๋น„์šฉ ์ด๋‚ด์— ํ•ด๋‹นํ•˜๋Š” ๋ชจ๋“  ๊ธˆ์•ก์œผ๋กœ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•œ๋‹ค๋Š” ์˜๋ฏธ์˜€๋‹ค.

์ถœ๋ฐœ ์ง€์ ์€ 1๋ฒˆ ๊ณตํ•ญ, 1๋ฒˆ ๊ณตํ•ญ์— ๋Œ€ํ•œ ๋น„์šฉ์€ 0์›, ์†Œ์š”์‹œ๊ฐ„๋„ 0์ด๋ฏ€๋กœ clock[1][0] = 0์ด ๋œ๋‹ค.

 

์ดํ›„ ๋‹ค์ต์ŠคํŠธ๋ผ์™€ ๊ฐ™๊ฒŒ ์กฐ๊ฑด์„ ํƒ์ƒ‰ํ•ด์„œ DP ๊ฐ’์„ ๋ณ€๊ฒฝํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

์ตœ์ข…์ ์œผ๋กœ ๋„์ฐฉ ๊ณตํ•ญ(=N)์˜ ์ตœ์†Œ๊ฐ’์„ ๋ฆฌํ„ดํ•ด์ฃผ๋ฉด ๋˜๋Š”๋ฐ ๊ทธ ์ด์œ ๋Š” ๊ฐ„๋‹จํ•˜๋‹ค.

DP๋Š” ํ˜„์žฌ 2์ฐจ์›๋ฐฐ์—ด๋กœ ์„ ์–ธ๋˜์–ด ์žˆ๋Š”๋ฐ MIN(DP[N])์„ ํ•˜๊ฒŒ ๋˜๋ฉด ๋„์ฐฉ ๊ณตํ•ญ์— ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ์†Œ ์†Œ์š” ์‹œ๊ฐ„์„ ์ฐพ์„ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ๋งŒ์•ฝ ์ด ๊ฐ’์ด INF์ธ ๊ฒฝ์šฐ ๋„์ฐฉ ๊ณตํ•ญ์— ๋„๋‹ฌํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์ด๋ฏ€๋กœ "Poor KCM"์„ ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค.

 

์‹คํŒจ์“ฐ... Python์œผ๋กœ๋Š” ํ†ต๊ณผ๊ฐ€ ์•ˆ๋œ๋‹ค.

์ด๋ž˜์„œ ๊ณจ๋“œ1 ๋ฌธ์ œ์˜€๋‚˜๋ณด๋‹ค. ์ƒ๊ฐ์„ ๋‘ ๋ฒˆ ํ•˜๊ฒŒ ๋งŒ๋“œ๋Š” ๋ฌธ์ œ๋‹ค. ๋ถ„๋ฐœํ•˜์ž.

 

ํŒŒ์ด์ฌ์œผ๋กœ ๊ตฌํ˜„ํ•œ ์ฝ”๋“œ์ด๋‹ค.

 

์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ > Shortest Path' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[์ตœ๋‹จ ๊ฒฝ๋กœ] [Python / C++] 1956. ์šด๋™ - GOLD โ…ฃ  (3) 2021.04.16
  1. ์ž…๋ ฅ
  2. ์ถœ๋ ฅ
  3. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•
'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Shortest Path' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [์ตœ๋‹จ ๊ฒฝ๋กœ] [Python / C++] 1956. ์šด๋™ - GOLD โ…ฃ
kodo_o
kodo_o
iOS ๊ฟ€์žผ!
kodo_o
๐ŸŽ๐Ÿ
kodo_o
์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (149)
    • ๐Ÿ”จ ํ”„๋กœ์ ํŠธ (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • ๐Ÿ’ป ๊ฐœ๋ฐœ (63)
      • iOS (30)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Architecture (1)
      • ์˜ค๋Š˜์˜ ์‚ฝ์งˆ (7)
      • ์—๋Ÿฌ์™€์˜ ๋™์นจ (1)
    • โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • ๐Ÿ“š CS (6)
      • Operating System (6)
    • โ›น๏ธ ๋ผ์ดํ”„ (30)
      • 2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (12)
      • 2021 ์—ฌ๋ฆ„๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (6)
      • ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ (1)
      • ํšŒ๊ณ  (10)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ๊นƒํ—ˆ๋ธŒ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

hELLO ยท Designed By ์ •์ƒ์šฐ.
kodo_o
[์ตœ๋‹จ ๊ฒฝ๋กœ] [Python] 10217. KCM Travel - GOLD โ… 
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.