deo2kim
๋งž์™œํ‹€
deo2kim
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • ๊ฐœ๋ฐœ
    • Infra

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

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

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

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
deo2kim

๋งž์™œํ‹€

ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ(Floyd Warshall)
CS/Algorithm

ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ(Floyd Warshall)

2020. 10. 4. 20:51
๋ฐ˜์‘ํ˜•

์ถœ์ฒ˜: https://blog.naver.com/ndb796/221234427842

๐Ÿ“” ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ(Floyd Warshall) ๋ž€

ํ”Œ๋กœ์ด๋“œ-์›Œ์…œ ์•Œ๊ณ ๋ฆฌ์ฆ˜(Floyd-Warshall Algorithm)์€ ๊ทธ๋ž˜ํ”„์—์„œ ๋ชจ๋“  ๊ผญ์ง“์  ์‚ฌ์ด์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์Œ์ˆ˜ ๊ฐ€์ค‘์น˜๋ฅผ ๊ฐ–๋Š” ๊ฐ„์„ ๋„ ์ˆœํ™˜๋งŒ ์—†๋‹ค๋ฉด ์ž˜ ์ฒ˜๋ฆฌ๋œ๋‹ค. ์ œ์ผ ๋ฐ”๊นฅ์ชฝ ๋ฐ˜๋ณต๋ฌธ์€ ๊ฑฐ์ณ๊ฐ€๋Š” ๊ผญ์ง“์ ์ด๊ณ , ๋‘ ๋ฒˆ์งธ ๋ฐ˜๋ณต๋ฌธ์€ ์ถœ๋ฐœํ•˜๋Š” ๊ผญ์ง“์ , ์„ธ ๋ฒˆ์งธ ๋ฐ˜๋ณต๋ฌธ์€ ๋„์ฐฉํ•˜๋Š” ๊ผญ์ง“์ ์ด๋‹ค. ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ”Œ๋กœ์ด๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ๊ณ ๋„ ์•Œ๋ ค์ ธ ์žˆ๋‹ค. ( ์ถœ์ฒ˜: ์œ„ํ‚ค๋ฐฑ๊ณผ )
  • ๋ชจ๋“  ์ •์ ์—์„œ ๋ชจ๋“  ์ •์ ์œผ๋กœ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ!
    • ๊ฑฐ์ณ๊ฐ€๋Š” ์ •์ ์„ ๊ธฐ์ค€์œผ๋กœ ๊ตฌํ•œ๋‹ค.
    • ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๊ธฐ๋ฒ•์„ ์ด์šฉ
    • ๋‹ค์ต์ŠคํŠธ๋ผ์˜ ๊ฒฝ์šฐ ํ•œ ์ •์ ์—์„œ ๋ชจ๋“  ์ •์ ๊นŒ์ง€ ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ
  • ๋ฐ˜๋ณต๋ฌธ์ด 3๊ฐœ์ด๋ฏ€๋กœ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(N^3) ์ด๋‹ค. ํ•˜์ง€๋งŒ ์ฝ”๋“œ๋Š” ๋งค์šฐ ๊ฐ„๋‹จํ•˜๋‹ค.

๐Ÿ“” ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ(Floyd Warshall) ๊ตฌํ˜„

  • ๊ฐ€์ค‘์น˜ ์ธ์ ‘ ํ–‰๋ ฌ์„ ๋งŒ๋“ ๋‹ค.

  • i ์—์„œ j ๋กœ ๊ฐˆ ๋•Œ์˜ ๊ฐ€์ค‘์น˜์ด๋‹ค.
  • inf๋Š” ๋ฌดํ•œ๋Œ€๋ผ๋Š” ๋œป์œผ๋กœ i ์™€ j๊ฐ€ ๋ฐ”๋กœ ์ด์–ด์ ธ ์žˆ์ง€ ์•Š๋‹ค๋Š” ์˜๋ฏธ
  • ์ด์ œ ๊ฑฐ์ณ๊ฐ€๋Š” ์ •์ ์„ ๊ธฐ์ค€์œผ๋กœ ์ธ์ ‘ ํ–‰๋ ฌ์„ ๊ฐฑ์‹ ํ•œ๋‹ค.
  • i ์—์„œ k๋ฅผ ๊ฑฐ์ณ j๋กœ ๊ฐ€๋Š” ๊ฒƒ๊ณผ i ์—์„œ ๋ฐ”๋กœ j๋กœ ๊ฐ€๋Š”๊ฒƒ
    adj[i][k] + adj[k][j] ์™€ adj[i][j] ๋ฅผ ๋น„๊ต
  • ๋‘˜ ์ค‘ ์ž‘์€๊ฒƒ์œผ๋กœ ์ธ์ ‘ ํ–‰๋ ฌ์„ ๊ฐฑ์‹ ํ•œ๋‹ค.
  • ๋ชจ๋“  ์ •์ ์— ๋Œ€ํ•ด์„œ ํ–‰ํ•˜๋ฏ€๋กœ 3์ค‘ ํฌ๋ฌธ์„ ์‚ฌ์šฉ
  • ๊ฒฐ๊ณผ ๊ฐ’์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค

# ๊ฐ€์ค‘์น˜ ์ธ์ ‘ํ–‰๋ ฌ  # ๋ฐ”๋กœ ์—ฐ๊ฒฐ์ด ์•ˆ๋ผ์žˆ๋Š” ๊ฒฝ์šฐ INF(๋ฌดํ•œ๋Œ€)
N = 4
INF = float('inf')
adj = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
]

print('๊ฐ€์ค‘์น˜ ์ธ์ ‘ ํ–‰๋ ฌ')
for row in adj:
    print(row)
print()

# ๊ฑฐ์ณ๊ฐ€๋Š” ์ •์  k๋ฅผ  ๊ธฐ์ค€์œผ๋กœ
for k in range(N):
    # ์ถœ๋ฐœ ์ •์  i ์—์„œ
    for i in range(N):
        # ๋„์ฐฉ ์ •์  j ๊นŒ์ง€
        for j in range(N):
            # i์—์„œ k๋ฅผ ๊ฑฐ์ณ j ๊นŒ์ง€ ๊ฐ€๋Š” ๊ฒƒ๊ณผ i์—์„œ j๊นŒ์ง€ ๋ฐ”๋กœ๊ฐ€๋Š” ๊ฒƒ์ค‘ ๊ฐ’์ด ๋” ์ž‘์€ ๊ฒƒ์œผ๋กœ ๊ฐฑ์‹ 
            adj[i][j] = min(adj[i][k] + adj[k][j], adj[i][j])

print('๊ฒฐ๊ณผ')
for row in adj:
    print(row)
print()
๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'CS > Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

ํž™ ์ •๋ ฌ(heap sort)  (0) 2020.10.06
์œ„์ƒ ์ •๋ ฌ(topology sort)  (0) 2020.10.05
์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด(Sieve Of Eratosthenes)  (0) 2020.10.03
๋‹ค์ต์ŠคํŠธ๋ผ(dijkstra)  (0) 2020.10.02
๋‹ค์ด๋‚˜๋ฏนํ”„๋กœ๊ทธ๋ž˜๋ฐ(Dynamic Programming)  (0) 2020.10.01
    'CS/Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • ํž™ ์ •๋ ฌ(heap sort)
    • ์œ„์ƒ ์ •๋ ฌ(topology sort)
    • ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด(Sieve Of Eratosthenes)
    • ๋‹ค์ต์ŠคํŠธ๋ผ(dijkstra)
    deo2kim
    deo2kim
    ์ฝ”๋”ฉ ๊ธฐ๋กํ•˜๊ธฐ

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