[백준] 13141번 Ignition ★★

💡문제접근

• 다익스트라 알고리즘과 플로이드-워셜 알고리즘 두 가지 알고리즘 중 플로이드-워셜 알고리즘을 선택했고 모든 정점에서 각각의 정점으로 갈 수 있는 최단거리를 2차원 리스트에 저장했다.
• 그런 다음 for문을 이용해서 1 ~ N번까지의 각각의 발화 경우를 모두 비교하여 어떤 점에서 불을 붙여야 모든 간선이 빠르게 타는지를 구하면 된다.

💡코드(메모리 : 34324KB, 시간 : 2784ms)

import sys
input = sys.stdin.readline
INF = int(1e9)

N, M = map(int, input().strip().split())
graph = [[INF] * (N+1) for _ in range(N+1)]
edges = []
for _ in range(M):
    S, E, L = map(int, input().strip().split())
    edges.append([S, E, L])
    if graph[S][E] > L:
        graph[S][E] = L
        graph[E][S] = L

for k in range(1, N + 1):
    graph[k][k] = 0
    for a in range(1, N + 1):
        for b in range(1, N + 1):
            if graph[a][b] > graph[k][a] + graph[k][b]:
                graph[a][b] = graph[k][a] + graph[k][b]

ans = INF
# ex. 1번에 불을 지른 경우
for i in range(1, N+1):
    cur = 0
    for edge in edges:
        S, E, L = edge
        # ex. 1 2 1
        # ex. 2 3 1
        # ex. 1 3 10
        # 2번에 불을 지르면 1번과 3번에 불이 붙는다.
        # 이 때, 2번에 불을 지르고 1초 뒤에 1번과 3번에 불이 붙어 1-2, 2-3 간선이 다 붙에 타게 된다.
        # 1-3 간선에서 1번과 3번 정점이 모두 불에 탔으므로 이 때는 간선의 양쪽에서 타던 것이 만나는 지점까지 탄다.
        # 양쪽에서 1초에 1만큼씩 타게 되면 1-3 간선의 길이가 10이므로 간선이 모두 타는데 걸리는 시간은 5가 된다.
        # 따라서 (1 + 1 + 10) / 2 = 6.0이 된다.
        tmp = (L + graph[i][S] + graph[i][E]) / 2
        if tmp > cur:
            cur = tmp
    if cur < ans:
        ans = cur
print(ans)

💡소요시간 : 2h 17m