โœ๐Ÿปํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ(Floyd Warshall) ์•Œ๊ณ ๋ฆฌ์ฆ˜

eunseo kim ๐Ÿ‘ฉโ€๐Ÿ’ปยท2021๋…„ 6์›” 26์ผ
0

โœจ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ธฐ๋ณธ

๋ชฉ๋ก ๋ณด๊ธฐ
10/10

๐Ÿ“ข๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ vs ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ : ํ•˜๋‚˜์˜ ์ •์ ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ์ •์ ์œผ๋กœ์˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ(์Œ์˜ ๊ฐ€์ค‘์น˜ ๋ถˆ๊ฐ€๋Šฅ)
  • ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ : ๋ชจ๋“  ์ •์ ์—์„œ ๋ชจ๋“  ์ •์ ์œผ๋กœ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜(์Œ์˜ ๊ฐ€์ค‘์น˜ ๊ฐ€๋Šฅ)

๐Ÿ’ก ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€?

  • ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ธ์ ‘ ํ–‰๋ ฌ ํ‘œ๊ธฐ๋ฒ•์„ ์‚ฌ์šฉํ•œ๋‹ค.

๐Ÿ‘๐Ÿปํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์–ด๋–ค ์•Œ๊ณ ๋ฆฌ์ฆ˜์ผ๊นŒ?

  • ์šฐ์„  ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทธ๋ž˜ํ”„๊ฐ€ ์žˆ๋‹ค๊ณ  ํ•ด๋ณด์ž!
  • ์ด ๊ทธ๋ž˜ํ”„๋ฅผ ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด ์•„๋ž˜์™€ ๊ฐ™๋‹ค.
  • ์šฐ๋ฆฌ๊ฐ€ ๊ถ๊ธˆํ•œ ๊ฒƒ์€ ๋ชจ๋“  ์ •์  ์‚ฌ์ด์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋กœ, ์ฆ‰ i๋ฒˆ ์ •์ ์—์„œ j๋ฒˆ ์ •์  ์‚ฌ์ด์˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ์ด๋‹ค. (์—ฌ๊ธฐ์„œ i, j๋Š” 1~4 ์‚ฌ์ด์˜ ์ž„์˜์˜ ์ˆซ์ž์ด๋‹ค.)
  • ๋”ฐ๋ผ์„œ, ๋ฏธ๋ฆฌ ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•œ ์ตœ์ข… ๊ฒฐ๊ณผ ๊ทธ๋ž˜ํ”„๋ฅผ ์‚ดํŽด๋ณด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.
  • ์œ„์˜ ํ–‰๋ ฌ์„ ํ•ด์„ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ํ–‰์ด i, ์—ด์ด j์ผ๋•Œ i๋ฒˆ ์ •์ ์—์„œ j๋ฒˆ ์ •์  ์‚ฌ์ด์˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ์ž„์„ ๊ธฐ์–ตํ•˜๋ฉด ๋œ๋‹ค.
  • ์˜ˆ๋ฅผ ๋“ค์–ด์„œ i=1, j=3์ผ๋•Œ ํ–‰๋ ฌ์˜ ๊ฐ’์„ ์ฝ์œผ๋ฉด -2์ด๋‹ค.
    ์ด๋Š” i๋ฒˆ ์ •์ ์—์„œ j๋ฒˆ ์ •์  ์‚ฌ์ด์˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” -2๋ผ๊ณ  ํ•ด์„ํ•˜๋ฉด ๋œ๋‹ค.

๐Ÿ‘๐Ÿปํ”Œ๋กœ์ด๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ•ต์‹ฌ

  • ํ•ต์‹ฌ โ˜ž adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

  • i์—์„œ j์‚ฌ์ด์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋ ค๋ฉด 2๊ฐ€์ง€ ๊ฒฝ์šฐ๋ฅผ ๋น„๊ตํ•ด์•ผ ๋œ๋‹ค. k๋ฅผ ๊ฒฝ์œ ์ง€(์ž„์˜์˜ ์ •์ )๋ผ๊ณ  ํ•˜์ž.
    1) ๊ฒฝ์œ ์ง€ k๋ฅผ ์ง€๋‚˜์ง€ ์•Š๋Š” ๊ฒฝ๋กœ (i โ†’ j)
    2) ๊ฒฝ์œ ์ง€ k๋ฅผ ์ง€๋‚˜๋Š” ๊ฒฝ๋กœ (i โ†’ k โ†’ j)

  • ๋”ฐ๋ผ์„œ ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ž„์˜์˜ (๊ฒฝ์œ ์ง€) ์ •์  k์— ๋Œ€ํ•ด์„œ k๋ฅผ ์ง€๋‚˜๋Š” ๊ฒฝ๋กœ vs k๋ฅผ ์ง€๋‚˜์ง€ ์•Š๋Š” ๊ฒฝ๋กœ ์ค‘์—์„œ ๋” ์ž‘์€ ๊ฐ’์„ ์ตœ๋‹จ ๊ฒฝ๋กœ๋กœ ์„ ํƒํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

  • ๋‘ ๊ผญ์ง“์  ๊ฐ„์˜ ์ถ”์ • ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ตœ์ ์ด ๋  ๋•Œ๊นŒ์ง€ ์ ์ง„์ ์œผ๋กœ ๊ฐœ์„ ์‹œ์ผœ์„œ ์ตœ๋‹จ๊ฒฝ๋กœ๋ฅผ ์ฐพ๋Š”๋‹ค.


๐Ÿ‘๐Ÿป์ง์ ‘ ์ฐจ๋ก€๋Œ€๋กœ ๊ตฌํ•ด๋ณด์ž!

  1. ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทธ๋ž˜ํ”„๋ฅผ ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ๋‚˜ํƒ€๋‚ธ๋‹ค.
  • ์˜ˆ์‹œ ๊ทธ๋ž˜ํ”„

โœ” ์ธ์ ‘ํ–‰๋ ฌ๋กœ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐฉ๋ฒ•

  • ์ž๊ธฐ์ž์‹ ์œผ๋กœ ๊ฐ€๋Š” ๊ฐ„์„ (i, i)์˜ ๊ฐ€์ค‘์น˜๋Š” 0์œผ๋กœ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.
  • ์•„์ง ๊ฒฝ๋กœ๊ฐ€ ์ง€์ •๋˜์ง€ ์•Š์€ ๊ฐ„์„  ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋Š” ๋ฌดํ•œ๋Œ€(โˆž)๋กœ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.
  • ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ๋‚˜ํƒ€๋‚ธ ๊ฒƒ

  1. ๊ฒฝ์œ ์ง€ k์— ๋Œ€ํ•ด ๊ฒฝ์œ ์ง€k๋ฅผ ์ง€๋‚˜๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ vs ๊ฒฝ์œ ์ง€ k๋ฅผ ์ง€๋‚˜์ง€ ์•Š์„ ๋•Œ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๋น„๊ตํ•ด๋‚˜๊ฐ€์ž.
  • k = 1 / ๊ฒฝ์œ ์ง€๊ฐ€ <1>์ธ ๊ฒฝ์šฐ
    • 1 -> 1 vs 1 -> <1> -> 1
    • 1 -> 2 vs 1 -> <1> -> 2
      ... (์ƒ๋žต)
    • 2 -> 3 vs 2 -> <1> -> 3 โญ๊ฒฝ์œ ์ง€๋ฅผ ์ง€๋‚  ๋•Œ๊ฐ€ ๋” ์ตœ์†Ÿ๊ฐ’์ด๋ฏ€๋กœ ๊ฐฑ์‹ ํ•œ๋‹คโญ
      ... (์ƒ๋žต)
    • 4 -> 4 vs 4 -> <1> -> 4

  • k = 2 / ๊ฒฝ์œ ์ง€๊ฐ€ <2>์ธ ๊ฒฝ์šฐ
    • 1 -> 1 vs 1 -> <2> -> 1
    • 1 -> 2 vs 1 -> <2> -> 2
    • 1 -> 3 vs 1 -> <2> -> 3
      ... (์ƒ๋žต)
    • 4 -> 1 vs 4 -> <2> -> 1 โญ๊ฒฝ์œ ์ง€๋ฅผ ์ง€๋‚  ๋•Œ๊ฐ€ ๋” ์ตœ์†Ÿ๊ฐ’โญ
    • 4 -> 2 vs 4 -> <2> -> 2
    • 4 -> 3 vs 4 -> <2> -> 3 โญ๊ฒฝ์œ ์ง€๋ฅผ ์ง€๋‚  ๋•Œ๊ฐ€ ๋” ์ตœ์†Ÿ๊ฐ’โญ
    • 4 -> 4 vs 4 -> <2> -> 4

  • k = 3, k = 4์— ๋Œ€ํ•ด์„œ๋„ ๋ฐ˜๋ณตํ•˜๋ฉด ์ตœ์ข…์ ์œผ๋กœ ์•„๋ž˜๊ณผ ๊ฐ™์€ ๊ฒฐ๊ณผ๊ฐ€ ๋‚˜์˜จ๋‹ค!
  • ์ด๊ฒƒ์ด ๋ฐ”๋กœ ์ตœ์ข…์ ์œผ๋กœ ๋ชจ๋“  ์ •์  ์‚ฌ์ด์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ํ–‰๋ ฌ๋กœ ํ‘œํ˜„ํ•œ, ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ตœ์ข… ๊ฒฐ๊ณผ์ด๋‹ค :D

๐Ÿ‘๐Ÿปํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ฝ”๋“œ (python)

def make_graph(n, arr):
    # ์ž๊ธฐ์ž์‹ ์œผ๋กœ ๊ฐ€๋Š” ๊ฐ„์„ ์€ 0์œผ๋กœ, ๋‚˜๋จธ์ง€๋Š” ๋ฌดํ•œ๋Œ€๋กœ ์ดˆ๊ธฐํ™”
    graph = [[0 if (i == j) else float("inf") for i in range(n)] for j in range(n)]

    for u, v, w in arr:
        graph[u - 1][v - 1] = w

    return graph # ์ธ์ ‘ํ–‰๋ ฌ์œผ๋กœ ๋งŒ๋“  ํ›„ ๋ฆฌํ„ด


def floyd_warshall(n, arr):
    # 1. ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ๋‚˜ํƒ€๋‚ด๊ธฐ
    graph = make_graph(n, arr)

    # 2. [๊ฒฝ์œ ์ง€(k)๋ฅผ ์ง€๋‚˜๋Š” ์ตœ๋‹จ ๊ฑฐ๋ฆฌ] vs [๊ฒฝ์œ ์ง€(k)๋ฅผ ์ง€๋‚˜์ง€ ์•Š๋Š” ์ตœ๋‹จ ๊ฑฐ๋ฆฌ]
    # ๋‘ ๊ผญ์ง“์  ๊ฐ„์˜ ์ถ”์ • ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ตœ์ ์ด ๋  ๋•Œ๊นŒ์ง€ ์ ์ง„์ ์œผ๋กœ ๊ฐœ์„ ์‹œ์ผœ์„œ ์ตœ๋‹จ๊ฒฝ๋กœ๋ฅผ ์ฐพ์Œ.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

    return graph
   

โญ์ž…๋ ฅโญ

  • ์˜ˆ์‹œ๋กœ ์ด ๊ทธ๋ž˜ํ”„๋ฅผ ์ถœ๋ ฅํ•ด๋ด…์‹œ๋‹ค :D
# n์€ ์ •์  ๊ฐœ์ˆ˜ / arr์€ [์‹œ์ž‘ ์ •์ , ๋„์ฐฉ ์ •์ , ๊ฐ€์ค‘์น˜(๊ฑฐ๋ฆฌ)]
n = 4
arr = [[1, 3, -2], [3, 4, 2], [4, 2, -1], [2, 1, 4], [2, 3, 3]]
answer = floyd_warshall(n, arr)

# ์ถœ๋ ฅํ•ด๋ณด๊ธฐ
for ans in answer:
    print(ans)

โญ์ถœ๋ ฅโญ

  • ์ž˜ ๋‚˜์˜ค๋„ค์š” XD

profile
์—ด์‹ฌํžˆ๐Ÿ’จ (์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ธ”๋กœ๊ทธ)

0๊ฐœ์˜ ๋Œ“๊ธ€