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

Programming/Algorithm

[Algorithm] ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ(Floyd Warshall) ์•Œ๊ณ ๋ฆฌ์ฆ˜(ft.ํŒŒ์ด์ฌ)

728x90
๋ฐ˜์‘ํ˜•

๐Ÿšฉ ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํŒŒ์ด์ฌ ๊ตฌํ˜„

ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ์€ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๊ฐ™์ด ์ตœ๋‹จ๊ฑฐ๋ฆฌ ํ˜น์€ ์ตœ์†Œ๋น„์šฉ์„ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค.

ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ์€ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ๋Š” ๋‹ฌ๋ฆฌ ๋ชจ๋“  ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ๋…ธ๋“œ๋“ค๊นŒ์ง€์˜ ์ตœ์†Œ ๊ฑฐ๋ฆฌ(ํ˜น์€ ์ตœ์†Œ๋น„์šฉ)์„ ๊ตฌํ•˜๊ธฐ ๋•Œ๋ฌธ์— "์–ด๋”˜๊ฐ€๋ฅผ ๊ฒฝ์œ ํ•œ๋‹ค."๋ผ๋Š” ์กฐ๊ฑด์ด ์ฃผ์–ด์งˆ ๋•Œ, ์‚ฌ์šฉ์„ ๊ณ ๋ คํ•˜๊ธฐ ์ข‹์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž…๋‹ˆ๋‹ค.

 

๋‹ค๋งŒ, ์ถœ๋ฐœ์ (s), ๋„์ฐฉ์ง€์ (e), ๊ฒฝ์œ ์ง€(p)์— ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๊ณ ๋ คํ•ด์•ผํ•˜๋ฏ€๋กœ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(N^3)์œผ๋กœ ํฐ ํŽธ ์ž…๋‹ˆ๋‹ค.

์ฆ‰, ๋ฌธ์ œ์—์„œ ์ฃผ์–ด์ง„ ๋…ธ๋“œ(N)์˜ ์ตœ๋Œ“๊ฐ’์„ ๊ณ ๋ คํ•ด ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•ด ์‚ฌ์šฉํ•  ๊ฐ€์น˜๊ฐ€ ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ธ์ง€ ๊ณ ๋ คํ•ด๋ด์•ผํ•ฉ๋‹ˆ๋‹ค.

โœ๏ธ ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜

์œ„ ๊ทธ๋ฆผ์˜ ๊ฒฝ์šฐ๋Š” ์ถœ๋ฐœ์ง€์ ์ด 1๋ฒˆ ๋…ธ๋“œ, ๋„์ฐฉ์ง€์ ์ด 4๋ฒˆ ๋…ธ๋“œ์ธ ๊ฒฝ์šฐ ์ž…๋‹ˆ๋‹ค.

 

1 -> 4๋กœ ๊ฐ€๋Š”๊ฒŒ ๊ฒฝ์œ ์ง€ ์—†์ด ๊ฐ„๋‹ค๋ฉด ๋น„์šฉ์€ 4๊ฐ€ ๋“ค๊ฒŒ๋ฉ๋‹ˆ๋‹ค.

๋งŒ์•ฝ ๊ฒฝ์œ ์ง€๋ฅผ ์„ ํƒํ•˜๊ฒŒ ๋  ๋•Œ, 2๋ฒˆ์„ ๊ฒฝ์œ ์ง€๋กœ ์„ ํƒํ•œ๋‹ค๋ฉด ์ด ๋น„์šฉ์€ 3(2 + 1)์ด๊ณ  3์„ ๊ฒฝ์œ ์ง€๋กœ ์„ ํƒํ•œ๋‹ค๋ฉด ๋น„์šฉ์€ 2(1 + 1)์ด ๋ฉ๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ ์œ„ ๊ทธ๋ฆผ์˜ ์ตœ์†Œ ๋น„์šฉ(ํ˜น์€ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ)๋Š” 1 -> 3 -> 4๋ฅผ ์„ ํƒํ•œ 2๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

์ด์ œ๋ถ€ํ„ฐ 1 -> 4๋กœ ์ด๋™ํ•  ๋•Œ ๋ฐœ์ƒํ•˜๋Š” ์ตœ์†Œ๋น„์šฉ์€ 2๋ผ๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ์€ ์ด์ฒ˜๋Ÿผ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•ด์„œ ๋‹ค๋ฅธ ๋…ธ๋“œ๊นŒ์ง€์˜ ์ตœ์†Œ๋น„์šฉ์„ ๊ณ„์† ๊ฐฑ์‹ ํ•ด์ฃผ๋ฉด์„œ ๋ชจ๋“  ๋…ธ๋“œ์—์„œ ๋ชจ๋“  ๋…ธ๋“œ๊นŒ์ง€(๋ช‡ ๋ฒˆ์„ ๊ฒฝ์šฐํ•˜๋Š”์ง€ ์ƒ๊ด€์—†์ด) ์ตœ์†Œ ๋น„์šฉ์„ ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

โœ๏ธ ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ฝ”๋“œ(ํŒŒ์ด์ฌ)

cost = [[INF] * n for _ in range(n)]    # INF๋กœ ๊ตฌ์„ฑ๋œ n x n ํ–‰๋ ฌ, ๋…ธ๋“œ๋ผ๋ฆฌ์˜ ์ตœ์†Œ ๋น„์šฉ์„ ๋‹ด์„ ๋ฐฐ์—ด

for i in range(n):  # ์ž๊ธฐ์ž์‹  -> ์ž๊ธฐ์ž์‹ ์˜ ๋น„์šฉ์€ 0์ด๋ฏ€๋กœ ์ดˆ๊ธฐํ™” ํ•ด์ค€๋‹ค.
	cost[i][i] = 0

# ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ
    for k in range(n):  # ๊ฒฝ์œ ์ง€
        for j in range(n):  # ๋„์ฐฉ์ง€
            for i in range(n):  # ์ถœ๋ฐœ์ง€
                # ํ˜„์žฌ i -> j๊นŒ์ง€๋“œ๋Š” ๋น„์šฉ์ด i -> k -> j์˜ ๋น„์šฉ๋ณด๋‹ค ๋น„์‹ธ๋‹ค๋ฉด ๋” ์ €๋ ดํ•œ ๋น„์šฉ์œผ๋กœ ๊ฐฑ์‹ 
                if cost[i][j] > cost[i][k] + cost[k][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

์—ฌ๊ธฐ์„œ INF๋Š” ์ค‘๊ฐ„ ๊ฐ’์œผ๋กœ ์ฃผ์–ด์ง„ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋Š” ๊ฐ’๋ณด๋‹ค ํฐ ๊ฐ’์œผ๋กœ ์„ธํŒ…ํ•ฉ๋‹ˆ๋‹ค.

cost ๋ฐฐ์—ด์€ ์ถœ๋ฐœ์ง€์  -> ๋„์ฐฉ์ง€์  ๊นŒ์ง€์˜ ๋น„์šฉ์„ ๋‹ด์•„ ๋†“์„ 2์ฐจ์› ๋ฐฐ์—ด ์ž…๋‹ˆ๋‹ค.

 

์ถœ๋ฐœ์ , ๋„์ฐฉ์ , ๊ฒฝ์œ ์ง€๋ฅผ ๋ชจ๋‘ ํƒ์ƒ‰ํ•˜๋Š” 3์ฐจ์› for๋ฌธ์„ ๋Œ๋ฉด์„œ ํ˜„์žฌ์˜ ๋น„์šฉ(i -> j)๋ณด๋‹ค k๋ฅผ ๊ฒฝ์šฐํ•˜๋Š” (i -> k -> j) ๋น„์šฉ์ด ๋” ์ €๋ ดํ•˜๋‹ค๋ฉด ๊ฐฑ์‹ ํ•ด ์ฃผ๋ฉด ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ๊ตฌํ˜„์ด ์™„๋ฃŒ ๋ฉ๋‹ˆ๋‹ค.

 

์ด๋•Œ, ๊ฒฝ์œ ์ง€๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ชจ๋“  ๊ฒฝ์šฐ(์ถœ๋ฐœ, ๋„์ฐฉ)์„ ํ™•์ดํ•ด์•ผํ•˜๋ฏ€๋กœ ์ตœ์ƒ๋‹จ for๋ฌธ์—๋Š” ๊ฒฝ์œ ์ง€(k)๊ฐ€ ์™€์•ผํ•ฉ๋‹ˆ๋‹ค.

๊ทธ๋ ‡์ง€ ์•Š์„ ๊ฒฝ์šฐ, ๋ชจ๋“  ๊ฒฝ์šฐ์—์„œ ์ œ๋Œ€๋กœ ๊ฐฑ์‹ ๋˜์ง€ ์•Š์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

โœ๏ธ ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์–ด๋ณด๊ธฐ(2021๋…„ ์นด์นด์˜ค ์‹ ์ž… ์ฑ„์šฉ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ)

https://programmers.co.kr/learn/courses/30/lessons/72413

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ํ•ฉ์Šน ํƒ์‹œ ์š”๊ธˆ

6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4

programmers.co.kr

ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•ด์•ผํ•˜๋Š” ๋ฌธ์ œ์ธ 2021๋…„ ์นด์นด์˜ค ์‹ ์ž… ์ฑ„์šฉ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๋ฌธ์ œ๋ฅผ ๊ฐ€์ ธ์™”์Šต๋‹ˆ๋‹ค.

 

๐Ÿ“ ์ „์ฒด ์ฝ”๋“œ

# ํ•ฉ์Šน ํƒ์‹œ
# ํ”Œ๋กœ์ด๋“œ ๋งˆ์ƒฌ
def solution(n, s, a, b, fares):
    INF = 200 * 100000 + 1  # ์ตœ๋Œ€ ๋น„์šฉ
    cost = [[INF] * n for _ in range(n)]    # INF๋กœ ๊ตฌ์„ฑ๋œ n x n ํ–‰๋ ฌ, ๋…ธ๋“œ๋ผ๋ฆฌ์˜ ์ตœ์†Œ ๋น„์šฉ์„ ๋‹ด์„ ๋ฐฐ์—ด

    for i in range(n):  # ์ž๊ธฐ์ž์‹  -> ์ž๊ธฐ์ž์‹ ์˜ ๋น„์šฉ์€ 0์ด๋ฏ€๋กœ ์ดˆ๊ธฐํ™” ํ•ด์ค€๋‹ค.
        cost[i][i] = 0

    for f in fares:
        start_node = f[0] - 1   # ๋…ธ๋“œ์˜ ๋ฒˆํ˜ธ๊ฐ€ 1๋ถ€ํ„ฐ ์ฃผ์–ด์ง€๋ฏ€๋กœ index๋ฅผ ๋งž์ถ”๊ธฐ ์œ„ํ•ด์„œ 1์„ ๋นผ์ค€๋‹ค.
        end_node = f[1] - 1
        price = f[2]
        # ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ์ถœ๋ฐœ์  <-> ๋„์ฐฉ์ ์˜ ๋น„์šฉ๋“ค์„ ๋Œ€์ž…ํ•ด์ค€๋‹ค.
        cost[start_node][end_node] = price
        cost[end_node][start_node] = price

    # ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ
    for k in range(n):  # ๊ฒฝ์œ ์ง€
        for i in range(n):  # ์ถœ๋ฐœ์ 
            for j in range(n):  # ๋„์ฐฉ์ 
                # ํ˜„์žฌ i -> j๊นŒ์ง€๋“œ๋Š” ๋น„์šฉ์ด i -> k -> j์˜ ๋น„์šฉ๋ณด๋‹ค ๋น„์‹ธ๋‹ค๋ฉด ๋” ์ €๋ ดํ•œ ๋น„์šฉ์œผ๋กœ ๊ฐฑ์‹ 
                if cost[i][j] > cost[i][k] + cost[k][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

    answer = INF
    # ๋ชจ๋“  ๊ฒฝ์œ ์ง€๋ฅผ ํƒ์ƒ‰ํ•˜๋ฉฐ ์ตœ์†Œ ์š”๊ธˆ์„ ๊ฐฑ์‹ 
    for k in range(n):
        answer = min(answer, cost[s - 1][k] + cost[k][a - 1] + cost[k][b - 1])

    return answer

 

728x90
๋ฐ˜์‘ํ˜•