๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

2021๋…„ ์นด์นด์˜ค ์‹ ์ž… ์ฝ”๋”ฉํ…Œ์ŠคํŠธ

(1)
[Algorithm] ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ(Floyd Warshall) ์•Œ๊ณ ๋ฆฌ์ฆ˜(ft.ํŒŒ์ด์ฌ) ๐Ÿšฉ ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํŒŒ์ด์ฌ ๊ตฌํ˜„ ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ์€ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๊ฐ™์ด ์ตœ๋‹จ๊ฑฐ๋ฆฌ ํ˜น์€ ์ตœ์†Œ๋น„์šฉ์„ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ์€ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ๋Š” ๋‹ฌ๋ฆฌ ๋ชจ๋“  ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ๋…ธ๋“œ๋“ค๊นŒ์ง€์˜ ์ตœ์†Œ ๊ฑฐ๋ฆฌ(ํ˜น์€ ์ตœ์†Œ๋น„์šฉ)์„ ๊ตฌํ•˜๊ธฐ ๋•Œ๋ฌธ์— "์–ด๋”˜๊ฐ€๋ฅผ ๊ฒฝ์œ ํ•œ๋‹ค."๋ผ๋Š” ์กฐ๊ฑด์ด ์ฃผ์–ด์งˆ ๋•Œ, ์‚ฌ์šฉ์„ ๊ณ ๋ คํ•˜๊ธฐ ์ข‹์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž…๋‹ˆ๋‹ค. ๋‹ค๋งŒ, ์ถœ๋ฐœ์ (s), ๋„์ฐฉ์ง€์ (e), ๊ฒฝ์œ ์ง€(p)์— ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๊ณ ๋ คํ•ด์•ผํ•˜๋ฏ€๋กœ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(N^3)์œผ๋กœ ํฐ ํŽธ ์ž…๋‹ˆ๋‹ค. ์ฆ‰, ๋ฌธ์ œ์—์„œ ์ฃผ์–ด์ง„ ๋…ธ๋“œ(N)์˜ ์ตœ๋Œ“๊ฐ’์„ ๊ณ ๋ คํ•ด ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•ด ์‚ฌ์šฉํ•  ๊ฐ€์น˜๊ฐ€ ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ธ์ง€ ๊ณ ๋ คํ•ด๋ด์•ผํ•ฉ๋‹ˆ๋‹ค. โœ๏ธ ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์œ„ ๊ทธ๋ฆผ์˜ ๊ฒฝ์šฐ๋Š” ์ถœ๋ฐœ์ง€์ ์ด 1๋ฒˆ ๋…ธ๋“œ, ๋„์ฐฉ์ง€์ ์ด 4๋ฒˆ ๋…ธ๋“œ์ธ ๊ฒฝ์šฐ ์ž…๋‹ˆ๋‹ค. 1 -> 4๋กœ ๊ฐ€๋Š”๊ฒŒ ๊ฒฝ์œ ..

728x90