[백준] 14938번 서강그라운드(python)

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

14938번: 서강그라운드

 

1. 난이도 골드4 (🥇)

 

2. 문제 해결 방법

플로이드 워셜 알고리즘과 다익스트라 모두 사용할 수 있다.

 

플로이드의 시간복잡도가 더 크지만, n의 범위가 1부터 100까지라 문제 없을 것 같다고 판단해 플로이드로 풀었다.

 

1. 플로이드 알고리즘을 이용해 모든 정점에서 다른 정점으로 가는 최단 거리를 구한다.

 

2. 수색범위보다 작거나 같을 때, 다른 정점으로 이동하며 아이템의 개수를 더해준다. (이걸 지역 개수만큼 반복해준다.)

 

3. 최대 아이템 개수를 출력하면 된다.

 

3. 내가 작성한 코드(플로이드 워셜)

INF = int(1e9)

n,m,r = map(int,input().split()) #n지역개수 m수색범위 r길

items = list(map(int, input().split())) #길이 가지고 있는 아이템의 개수

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

for i in range(n+1): 
  for j in range(n+1):
    if i == j:
      maps[i][j] = 0

for i in range(r):
  a,b,c = map(int, input().split()) #a,b, 양 끝 지역 c 가중치
  maps[a][b] = c
  maps[b][a] = c

for k in range(n+1): #플로이드 워셜 알고리즘
  for i in range(n+1):
    for j in range(n+1):
      maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])

max_score = 0

for i in range(1,n+1): #각 정점에서 출발해서 얻을 수 있는 아이템 계산
  score = 0
  for j in range(1,n+1):
    if maps[i][j] <= m:
      score += items[j-1] #maps의 인덱스는 1부터, itmes는 0부터 시작이라 -1 해줌
  max_score = max(score, max_score) #최대 아이템 개수 출력

print(max_score)

 

 

4. 내가 작성한 코드(다익스트라)

import heapq
import sys

input = sys.stdin.readline

n, m, r = map(int, input().rstrip().split())  # n지역 m수색범위 r길의개수
INF = int(1e9)
point = list(map(int, input().rstrip().split()))
graph = [[] for _ in range(n+1)]

for _ in range(r): #양방향 도로 입력받기
    a,b,c = map(int, input().rstrip().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

def dij(start): #다익스트라
    distance = [INF] * (n + 1)
    distance[start] = 0
    q = []
    heapq.heappush(q,(0,start))

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            if distance[i[0]] > dist+i[1]:
                distance[i[0]] = dist + i[1]
                heapq.heappush(q,(distance[i[0]],i[0]))

    return distance

total_result = 0

for i in range(1,n+1): #각 원소마다 다익스트라를 돌려줌
    distance = dij(i)[1:] 
    result = 0
    for j in range(n): #수색범위보다 거리가 적으면 item 합해줌
        if distance[j] <= m:
            result+=point[j]
    total_result = max(total_result, result) #모든 원소가 획득가능한 item 중 max값 출력

print(total_result)