[백준] 14938 서강그라운드 (python 파이썬)

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

14938번: 서강그라운드

---

조건만 잘 생각하면 되는 착한 문제.

---

아이디어

1. 다익스트라

• 출발지로 부터 최단거리를 계산해서 수색 범위안에 들어가는지 확인하면 된다.
• 수색 범위안에 들어오면 아이템 개수를 더해주면 된다.
• 1 ~ n까지 for문으로 출발지를 바꾸면서 탐색하면 된다.

2. 플로이드 워셜

• 지역의 개수(100)가 적으므로 플로이드 워셜로 풀어도 시간초과에 걸리지 않는다.

---

전체 코드

다익스트라

import heapq
import sys
INF = int(1e9)
n, m, r = map(int, input().split())

items = [0] + [int(x) for x in sys.stdin.readline().split()]

graph = [[] for _ in range(n + 1)]

for _ in range(r):
    a, b, l = map(int, sys.stdin.readline().split())
    graph[a].append([b, l])
    graph[b].append([a, l])

def dijkstra(start):
    que = []
    heapq.heappush(que, (0, start))
    D[start] = 0

    while que:
        dist, now = heapq.heappop(que)
        if D[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < D[i[0]]:
                D[i[0]] = cost
                heapq.heappush(que, (cost, i[0]))

ans = 0
for i in range(1, n + 1):
    D = [INF] * (n + 1)
    dijkstra(i)
    tmp = 0
    for d in range(1, n + 1):
        if m >= D[d]:
            tmp += items[d]

    ans = max(ans, tmp)

print(ans)

 

플로이드 워셜

import sys
INF = int(1e9)
n, m, r = map(int, input().split())

items = [0] + [int(x) for x in sys.stdin.readline().split()]

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for _ in range(r):
    a, b, l = map(int, sys.stdin.readline().split())
    graph[a][b] = l
    graph[b][a] = l

for i in range(n + 1):
    graph[i][i] = 0

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

ans = 0
for i in range(1, n + 1):
    tmp = 0
    for j in range(1, n + 1):
        if graph[i][j] <= m:
            tmp += items[j]

    ans = max(ans, tmp)

print(ans)

 

---

코드 설명

다익스트라

ans = 0
for i in range(1, n + 1):
    D = [INF] * (n + 1)
    dijkstra(i)
    tmp = 0
    for d in range(1, n + 1):
        if m >= D[d]:
            tmp += items[d]

    ans = max(ans, tmp)

print(ans)

for문을 사용해서 각 출발지 마다 얼마나 아이템을 모을 수 있는지 계산한다.

 

저장한 최댓값을 출력해주면 된다.

 

플로이드 워셜

ans = 0
for i in range(1, n + 1):
    tmp = 0
    for j in range(1, n + 1):
        if graph[i][j] <= m:
            tmp += items[j]

    ans = max(ans, tmp)

위와 방식은 똑같다.