BOJ
[Python 3] BOJ - 14938 "서강그라운드"
PeiSea
2020. 3. 26. 20:02
# 문제 링크 : https://www.acmicpc.net/problem/14938
14938번: 서강그라운드
예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는
www.acmicpc.net
# 풀이 :
개인적으로 문제의 핵심은 다익스트라 알고리즘을 유추할 수 있는지라고 생각한다. 다익스트라 알고리즘은 출발 정점에서 다른 모든 정점으로 갈 수 있는 최단 거리를 리턴하기 때문에, 모든 정점에 대해 다익스트라 알고리즘을 실행한 후, 만일 입력으로 주어진 수색범위안에 있다면 해당 정점으로 갈 수 있으므로 그때의 정점에 해당하는 아이템을 더해주면 되고, 각 정점에서 얻을 수 있는 모든 아이템들을 비교하여 최대값을 갱신하면 올바른 정답을 구할 수 있다.
# 코드
# 다익스트라의 빠른 실행을 위해 heapq 모듈 import
import heapq, sys
# 최대값 할당
INF = 99999999999999999999999
# 입력부
vertex, limit, edge = map(int, sys.stdin.readline().split())
item = list(map(int, sys.stdin.readline().split()))
# 인접 리스트 생성
adj = [[] for _ in range(vertex)]
for i in range(edge):
x,y,z = map(int, sys.stdin.readline().split())
adj[x - 1].append((y - 1, z))
adj[y - 1].append((x - 1, z))
# dijkstra : 다익스트라 알고리즘 함수
def dijstra(v):
d[v] = 0
min_q = []
min_q.append((d[v], v))
while len(min_q) != 0:
distance = min_q[0][0]
current = min_q[0][1]
heapq.heappop(min_q)
if d[current] < distance:
continue
for i in range(len(adj[current])):
next = adj[current][i][0]
nextdistance = adj[current][i][1] + distance
if nextdistance < d[next]:
d[next] = nextdistance
heapq.heappush(min_q, (nextdistance, next))
# 각 정점에 대해 다익스트라 실행
ans = 0
for i in range(vertex):
d = [INF] * vertex
dijstra(i)
cnt = item[i]
for j in range(vertex):
# 만일 j가 i가 아니고 수색범위 이내라면
# cnt에 정점 j에서 얻을 수 있는 아이템 수를 더해줌
if d[j] != 0 and d[j] <= limit:
cnt += item[j]
# 최대값 갱신
if ans < cnt:
ans = cnt
print(ans)