๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•

1753 python1

[๋ฐฑ์ค€] 1753. ์ตœ๋‹จ๊ฒฝ๋กœ/Python - ๊ณจ๋“œ4 โ“๋ฌธ์ œ์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 136204 KB, ์‹œ๊ฐ„: 380 ms๋ถ„๋ฅ˜๋‹ค์ต์ŠคํŠธ๋ผ, ๊ทธ๋ž˜ํ”„ ์ด๋ก , ์ตœ๋‹จ ๊ฒฝ๋กœ ๋ฌธ์ œ ์„ค๋ช…๋ฐฉํ–ฅ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ์ฃผ์–ด์ง„ ์‹œ์ž‘์ ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ์ •์ ์œผ๋กœ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋‹จ, ๋ชจ๋“  ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜๋Š” 10 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.โœ๐Ÿปํ’€์ด์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด ์ธ์ ‘ํ–‰๋ ฌ๊ณผ ์ธ์ ‘๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ ์ธ์ ‘ ํ–‰๋ ฌ์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ, ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(V²)์ด ๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(E * logV)์ด ๋˜๋ฏ€๋กœ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•ด์„œ ํ’€๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‹ค์ต์ŠคํŠธ๋ผ๋Š” Heap์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์ด ๋น ๋ฆ…๋‹ˆ๋‹ค.heapq๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด pq๋ฅผ ์ƒ์„ฑํ•ด (๊ฐ€์ค‘์น˜, ์‹œ์ž‘ ์ •์ ) ์Œ์œผ๋กœ ํž™ํ์— ๋„ฃ์–ด์ค€๋‹ค. ๊ทธ๋ฆฌ๊ณ  dist๋Š” ๊ฐ ์ •์ ์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์„ .. 2025. 1. 20.
728x90
๋ฐ˜์‘ํ˜•

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