[๋ฐฑ์ค€] 11404 ํ”Œ๋กœ์ด๋“œ (python ํŒŒ์ด์ฌ)

2022. 6. 18. 12:24ยท๐Ÿงฉ Problem Solving/[๋ฐฑ์ค€]

https://www.acmicpc.net/problem/11404

 

11404๋ฒˆ: ํ”Œ๋กœ์ด๋“œ

์ฒซ์งธ ์ค„์— ๋„์‹œ์˜ ๊ฐœ์ˆ˜ n์ด ์ฃผ์–ด์ง€๊ณ  ๋‘˜์งธ ์ค„์—๋Š” ๋ฒ„์Šค์˜ ๊ฐœ์ˆ˜ m์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์…‹์งธ ์ค„๋ถ€ํ„ฐ m+2์ค„๊นŒ์ง€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฒ„์Šค์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋จผ์ € ์ฒ˜์Œ์—๋Š” ๊ทธ ๋ฒ„์Šค์˜ ์ถœ๋ฐœ ๋„์‹œ์˜ ๋ฒˆํ˜ธ๊ฐ€

www.acmicpc.net

ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์“ฐ๋Š” ๋ฌธ์ œ.

๋ชจ๋“  ๋…ธ๋“œ ์Œ์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(N^3)

 

ํ’€์ด๊ณผ์ •

cost = [[INF for _ in range(N + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i == j:
            cost[i][j] = 0

for i in range(m):
    a, b, c = map(int,sys.stdin.readline().rstrip().split())
    if cost[a][b] > c:
        cost[a][b] = c

๋จผ์ € ๋ฐ์ดํ„ฐ ์ „์ฒ˜๋ฆฌ๋ฅผ ํ•ด์ค€๋‹ค. ์ž๊ธฐ์ž์‹ ๊ณผ์˜ ๊ฑฐ๋ฆฌ๋Š” 0์œผ๋กœ ์ดˆ๊ธฐํ™” ํ•ด์ฃผ๊ณ  ๋‚˜๋จธ์ง€๋Š” ์ฃผ์–ด์ง„ ์ž…๋ ฅ๊ฐ’์„ ๋„ฃ์–ด์ค€๋‹ค.

๋ฌธ์ œ์—์„œ "์‹œ์ž‘ ๋„์‹œ์™€ ๋„์ฐฉ ๋„์‹œ๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ๋…ธ์„ ์€ ํ•˜๋‚˜๊ฐ€ ์•„๋‹ ์ˆ˜ ์žˆ๋‹ค." ๋ผ๊ณ  ํ–ˆ์œผ๋ฏ€๋กœ ๋…ธ๋“œ์‚ฌ์ด ๊ฑฐ๋ฆฌ์ค‘ ์ตœ์†Œ๊ฐ’์„ ๋„ฃ๋„๋ก ํ•œ๋‹ค.

 

for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j])

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

์ถœ๋ฐœ์  i, ๋„์ฐฉ์  j ๊ทธ๋ฆฌ๊ณ  ์ค‘๊ฐ„์— ๊ฑฐ์ณ๊ฐ€๋Š” ์ง€์  k ๊ฐ€ ์žˆ์„๋•Œ, ๊ธฐ์กด์— ์žˆ๋˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ(cost[i][j])์™€ k๋ฅผ ๊ฑฐ์ณ๊ฐ€๋Š” ์ตœ๋‹จ๊ฑฐ๋ฆฌ(cost[i][k] + cost[k][j]) ๋ฅผ ๋น„๊ตํ•ด์„œ ์ตœ์†Œ๊ฐ’์„ ์—…๋ฐ์ดํŠธ ํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

 

 

์ „์ฒด ์ฝ”๋“œ

import sys
INF = int(1e9)
N = int(input())
m = int(input())
bus = []

cost = [[INF for _ in range(N + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i == j:
            cost[i][j] = 0

for i in range(m):
    a, b, c = map(int,sys.stdin.readline().rstrip().split())
    if cost[a][b] > c:
        cost[a][b] = c

for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j])

# print(cost)

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if cost[i][j] == int(1e9):
            print(0, end=' ')
        else:
            print(cost[i][j],end=' ')
    print()

'๐Ÿงฉ Problem Solving > [๋ฐฑ์ค€]' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€] 1389 ์ผ€๋นˆ ๋ฒ ์ด์ปจ์˜ 6๋‹จ๊ณ„ ๋ฒ•์น™ (python ํŒŒ์ด์ฌ)  (0) 2022.06.19
[๋ฐฑ์ค€] 7562 ๋‚˜์ดํŠธ์˜ ์ด๋™ (python ํŒŒ์ด์ฌ)  (0) 2022.06.18
[๋ฐฑ์ค€] 17070 ํŒŒ์ดํ”„ ์˜ฎ๊ธฐ๊ธฐ 1 (python ํŒŒ์ด์ฌ)  (0) 2022.06.16
[๋ฐฑ์ค€] 10026 ์ ๋ก์ƒ‰์•ฝ(python ํŒŒ์ด์ฌ)  (0) 2022.06.15
[๋ฐฑ์ค€] 1655 ๊ฐ€์šด๋ฐ๋ฅผ๋งํ•ด์š” (python ํŒŒ์ด์ฌ)  (0) 2022.06.14
'๐Ÿงฉ Problem Solving/[๋ฐฑ์ค€]' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€] 1389 ์ผ€๋นˆ ๋ฒ ์ด์ปจ์˜ 6๋‹จ๊ณ„ ๋ฒ•์น™ (python ํŒŒ์ด์ฌ)
  • [๋ฐฑ์ค€] 7562 ๋‚˜์ดํŠธ์˜ ์ด๋™ (python ํŒŒ์ด์ฌ)
  • [๋ฐฑ์ค€] 17070 ํŒŒ์ดํ”„ ์˜ฎ๊ธฐ๊ธฐ 1 (python ํŒŒ์ด์ฌ)
  • [๋ฐฑ์ค€] 10026 ์ ๋ก์ƒ‰์•ฝ(python ํŒŒ์ด์ฌ)
์ œ๋ด‰์•„
์ œ๋ด‰์•„
  • ์ œ๋ด‰์•„
    Overthinking
    ์ œ๋ด‰์•„
    fake it till you make it.
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (104)
      • ๐Ÿงฉ Problem Solving (83)
        • [๋ฐฑ์ค€] (74)
        • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] (7)
        • [SW Expert Academy] (1)
        • [์•Œ๊ณ ๋ฆฌ์ฆ˜ for PS] (1)
      • ๐Ÿ“ฆ Data Structure (2)
      • ๐Ÿ“œ Language (14)
        • [python] (14)
      • ๐Ÿ–ค Git (1)
      • ๐ŸŒ† ์ผ์ƒ (2)
        • ๐Ÿ’ฌ ๋ฒฝ๋ณด๊ณ  ๋งํ•˜๊ธฐ (2)
      • ๐Ÿ—„๏ธ ๊ธฐํƒ€ (2)
      • ๐Ÿ”ต css (0)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

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

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

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    ๋ƒ…์ƒ‰
    boj
    ๊ทธ๋ฆฌ๋””
    ๋ธŒ๋ฃจํŠธํฌ์Šค
    DP
    ์Šคํƒ
    ํˆฌํฌ์ธํ„ฐ
    ๋ถ€๋ถ„ํ•ฉ
    ๋ˆ„์ ํ•ฉ
    ๋ถ„ํ•  ์ •๋ณต
    ๊ตฌํ˜„
    ๋ฐฑํŠธ๋ž˜ํ‚น
    slicing
    ๋ฐฑ์ค€
    imos
    Bruteforce
    ์œ„์ƒ์ •๋ ฌ
    ํ”Œ๋กœ์ด๋“œ์›Œ์…œ
    ๋ฐ๋ธŒ์ฝ”์Šค
    DFS
    ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
    ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ
    ์žฌ๊ท€
    SWEA
    BFS
    ํŒŒ์ด์ฌ
    Python
    ๋‹ค์ต์ŠคํŠธ๋ผ
    ํŒฐ๋ฆฐ๋“œ๋กฌ
    ์ •์ฒ˜๊ธฐ
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • ์ตœ๊ทผ ๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
์ œ๋ด‰์•„
[๋ฐฑ์ค€] 11404 ํ”Œ๋กœ์ด๋“œ (python ํŒŒ์ด์ฌ)
์ƒ๋‹จ์œผ๋กœ

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