[백준] 14928 서강 그라운드

문제

• N개의 지역은 R개의 길로 연결되어 있다,
• 각 길은 일정한 길이 L의 양방향 통행이 가능한 길이다.
• 낙하 지역 중심으로 거리가 수색범위 M 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 얻을 수 있는 아이템의 최대 개수 구하기
• 1 <= N <= 100
  1 <= M, L <= 15
  1 <= R <= 100

 

풀이

• 모든 지역에서 수색범위 M이내로 갈 수 있는 다른 지역의 아이템 개수 합 구하기
  BFS를 사용하고, 아래 두 경우에 대해 큐에 추가된다.
  
  • 1) 처음 방문하는 곳이고, M 거리 이내에 방문 가능한 경우
  • 2) 이미 방문한 곳이나 더 짧은 거리로 방문이 가능한 경우

 

from collections import deque

N, M, R = map(int, input().split())
items = [0] + list(map(int, input().split()))
graph = [[] for _ in range(N+1)]
for _ in range(R) :
    a, b, l = map(int, input().split())
    graph[a].append((b, l))
    graph[b].append((a, l))

# 모든 지역에서 거리 M이내의 지역으로 이동하기
answer = [0] * (N+1)
for i in range(1, N+1) :
    q = deque([(i, 0)])
    visited = dict({i : 0})
    
    while q:
        now, dist = q.popleft()

        for x, d in graph[now] :
            # 더 짧은 거리로 방문이 가능하거나, M거리 이내에 방문 가능한 경우
            if (x in visited and visited[x] > d+dist) or (x not in visited and dist+d <= M) :
                visited[x] = d+dist
                q.append((x, dist+d))
    # 아이템 개수 구하기
    for k in visited :
        answer[i] += items[k]

# 최댓값 출력
print(max(answer))

 

References

• 백준 최단 거리