[BOJ][๐ŸŸก4][๋ฐฑ์ค€#11404] ํ”Œ๋กœ์ด๋“œ

์ž‘์„ฑ:    

์—…๋ฐ์ดํŠธ:

์นดํ…Œ๊ณ ๋ฆฌ:

ํƒœ๊ทธ: , , ,

๋ฌธ์ œ ์ถœ์ฒ˜

BAEKJOON Online Judge #11404


๋ฌธ์ œ

n(2ย โ‰ค n โ‰ค 100)๊ฐœ์˜ ๋„์‹œ๊ฐ€ ์žˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํ•œ ๋„์‹œ์—์„œ ์ถœ๋ฐœํ•˜์—ฌ ๋‹ค๋ฅธ ๋„์‹œ์— ๋„์ฐฉํ•˜๋Š” m(1 โ‰ค m โ‰ค 100,000)๊ฐœ์˜ ๋ฒ„์Šค๊ฐ€ ์žˆ๋‹ค. ๊ฐ ๋ฒ„์Šค๋Š” ํ•œ ๋ฒˆ ์‚ฌ์šฉํ•  ๋•Œ ํ•„์š”ํ•œ ๋น„์šฉ์ด ์žˆ๋‹ค. ๋ชจ๋“  ๋„์‹œ์˜ ์Œ (A, B)์— ๋Œ€ํ•ด์„œ ๋„์‹œ A์—์„œ B๋กœ ๊ฐ€๋Š”๋ฐ ํ•„์š”ํ•œ ๋น„์šฉ์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.


์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ๋„์‹œ์˜ ๊ฐœ์ˆ˜ n์ด ์ฃผ์–ด์ง€๊ณ  ๋‘˜์งธ ์ค„์—๋Š” ๋ฒ„์Šค์˜ ๊ฐœ์ˆ˜ m์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์…‹์งธ ์ค„๋ถ€ํ„ฐ m+2์ค„๊นŒ์ง€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฒ„์Šค์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋จผ์ € ์ฒ˜์Œ์—๋Š” ๊ทธ ๋ฒ„์Šค์˜ ์ถœ๋ฐœ ๋„์‹œ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋ฒ„์Šค์˜ ์ •๋ณด๋Š” ๋ฒ„์Šค์˜ ์‹œ์ž‘ ๋„์‹œ a, ๋„์ฐฉ ๋„์‹œ b, ํ•œ ๋ฒˆ ํƒ€๋Š”๋ฐ ํ•„์š”ํ•œ ๋น„์šฉ c๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์‹œ์ž‘ ๋„์‹œ์™€ ๋„์ฐฉ ๋„์‹œ๊ฐ€ ๊ฐ™์€ ๊ฒฝ์šฐ๋Š” ์—†๋‹ค. ๋น„์šฉ์€ 100,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์‹œ์ž‘ ๋„์‹œ์™€ ๋„์ฐฉ ๋„์‹œ๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ๋…ธ์„ ์€ ํ•˜๋‚˜๊ฐ€ ์•„๋‹ ์ˆ˜ ์žˆ๋‹ค.


์ถœ๋ ฅ

n๊ฐœ์˜ ์ค„์„ ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค. i๋ฒˆ์งธ ์ค„์— ์ถœ๋ ฅํ•˜๋Š” j๋ฒˆ์งธ ์ˆซ์ž๋Š” ๋„์‹œ i์—์„œ j๋กœ ๊ฐ€๋Š”๋ฐ ํ•„์š”ํ•œ ์ตœ์†Œ ๋น„์šฉ์ด๋‹ค. ๋งŒ์•ฝ, i์—์„œ j๋กœ ๊ฐˆ ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” ๊ทธ ์ž๋ฆฌ์— 0์„ ์ถœ๋ ฅํ•œ๋‹ค.


์˜ˆ์ œ

์ž…๋ ฅ

5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4


์ถœ๋ ฅ

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0


My Sol

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
mat = [[1e8]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    if mat[a][b] > c:
        mat[a][b] = c

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if i != j and mat[i][j] > mat[i][k] + mat[k][j]:
                mat[i][j] = mat[i][k] + mat[k][j]

for i in range(1, N+1):
    for j in range(1, N+1):
        if mat[i][j] == 1e8:
            mat[i][j] = 0
        print(mat[i][j], end=' ')
    print()

์‹œ๋„ํ–ˆ๋˜ ๋‹ค๋ฅธ ๋ฌธ์ œ์—์„œ ํ”Œ๋กœ์ด๋“œ ์›Œ์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ฒ˜์Œ์œผ๋กœ ์•Œ๊ฒŒ ๋˜์–ด ์ด๋ฅผ ์ฐธ๊ณ ํ•ด์„œ ํ’€์—ˆ๋‹ค. ํ”Œ๋กœ์ด๋“œ ์›Œ์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ O(N3)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค. n๊ฐœ์˜ ๋…ธ๋“œ๊ฐ€ ์žˆ์„ ๋•Œ n๋ฒˆ๋™์•ˆ i์—์„œ j๋ฅผ ๋ฐ”๋กœ ๊ฐˆ ๊ฒƒ์„ ๋‹ค๋ฅธ ๊ฒฝ๋กœ๋กœ ๊ฒฝ์œ ์—์„œ ๋” ๋น ๋ฅธ ๊ฒฝ๋กœ๊ฐ€ ์žˆ์„ ๊ฒƒ์ธ์ง€๋ฅผ ํŒ๋‹จํ•˜๋Š” ๊ฒƒ์ด๋‹ค. 3์ค‘ for๋ฌธ์„ ๋Œ๋ฆฌ๋ฉฐ ๋Œ์•„์„œ ๊ฐ„ ๊ฒฝ๋กœ๊ฐ€ ์ง์„  ๊ฒฝ๋กœ๋ณด๋‹ค ๋น ๋ฅธ ๊ฒฝ์šฐ ์ด๋ฅผ ๊ฐฑ์‹ ํ•ด์ฃผ๋Š” ๋ฐฉ์‹์ด๋‹ค.


๊ฒฐ๊ณผ

๋งž์•˜์Šต๋‹ˆ๋‹ค!!

3๋‹ฌ ์ „์— ์ด ๋ฌธ์ œ๋ฅผ multi dijkstra ๋ฌธ์ œ๋ผ๊ณ  ์ ์–ด๋‘๊ณ  ๋„˜์–ด๊ฐ”์—ˆ๋Š”๋ฐ, ํ•ด๊ฒฐ์ฑ…์„ ์šฐ์—ฐํžˆ ์•Œ๊ฒŒ๋˜๋‹ˆ ๊ธฐ๋ถ„์ด ์ข‹๋‹ค. ์—ญ์‹œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋‹ต์„ ๋ณด๋ฉฐ ์„ฑ์žฅํ•˜๋Š” ๊ฒƒ ๊ฐ™๋‹ค.

๋Œ“๊ธ€๋‚จ๊ธฐ๊ธฐ