[백준/Python] 14938번: 서강그라운드

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

14938번: 서강그라운드

---

---

문제 분석

예은이의 위치에 따라 수색범위 안에서 방문할 수 있는 지역을 모두 탐색한 뒤, 그 지역에서 얻을 수 있는 아이템들의 합을 구하는 문제이다.

플로이드-워셜 대표적인 문제라고 볼 수 있을 것 같다. [플로이드-워셜 알고리즘]

하지만 알고리즘 분류를 보기 전에는 그래프 탐색만으로 충분히 풀 수 있어 보여서 그래프 탐색을 이용한 풀이를 작성하고자 한다.

 

우선, 모든 노드를 탐색하면서 그 노드에서 출발하여 다른 노드까지의 거리를 모두 구한 뒤, 수색 범위에 들어오는 곳의 아이템 수를 누적하여 최댓값을 비교하여 구하였다.

 

def bfs(i):
    queue = deque()
    queue.append((i, 0))
    distance[i] = 0

    while queue:
        cur, now_dis = queue.popleft()

        for adj in graph[cur]:
            if distance[adj[0]] > now_dis + adj[1]:
                queue.append((adj[0], now_dis + adj[1]))
                distance[adj[0]] = now_dis + adj[1]

    return

위의 코드는 distance라는 배열에 최소 거리를 저장하는 함수이다.

 

처음 distance는 n개의 노드만큼 INF라는 sys 모듈을 통해 최댓값으로 설정해주고 그보다 작은 값이 되면 갱신해주게 된다.

 

---

코드

import sys
from collections import deque

input = sys.stdin.readline
INF = sys.maxsize


# 거리 갱신 함수
def bfs(i):
    queue = deque()
    queue.append((i, 0))
    distance[i] = 0

    while queue:
        cur, now_dis = queue.popleft()

        for adj in graph[cur]:
            if distance[adj[0]] > now_dis + adj[1]:
                queue.append((adj[0], now_dis + adj[1]))
                distance[adj[0]] = now_dis + adj[1]

    return


n, m, r = map(int, input().split())

items = 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))

answer = 0

# 1번 노드부터 탐색
for i in range(1, n + 1):
	# 최초 거리는 INF
    distance = [INF for _ in range(n + 1)]
	
    # 함수를 통해 거리를 최소로 갱신
    bfs(i)
	
    # temp라는 변수에 거리가 수색범위 안에 있는 노드의 아이템 수를 누적
    temp = 0
    for j in range(1, n + 1):
        if distance[j] <= m:
            temp += items[j - 1]
	
    # 현재 아이템 수와 비교하여 최댓값 갱신
    answer = max(answer, temp)

print(answer)