[알고리즘] 백준 - 서강그라운드

백준 - 서강그라운드

내 풀이 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class baekjoon_14938 {

    static int n, m, r;
    static List<int[]>[] graph;
    static int[] items;
    static int max_item = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]); //지역의 개수
        m = Integer.parseInt(inputs[1]); //수색 범위
        r = Integer.parseInt(inputs[2]); //길의 개수

        graph = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }
        items = new int[n+1];

        inputs = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            items[i+1] = Integer.parseInt(inputs[i]);
        }

        for (int i = 0; i < r; i++) {
            inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);
            int c = Integer.parseInt(inputs[2]);
            graph[a].add(new int[]{c, b});
            graph[b].add(new int[]{c, a});
        }
        for (int i = 1; i < n + 1; i++) {
            dijkstra(i);
        }
        System.out.println(max_item);
    }

    private static void dijkstra(int startNode) {
        int[] distances = new int[n + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[startNode] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] < o2[0] ? -1 : o1[0] == o2[0] ? 0 : 1;
            }
        });
        pq.add(new int[]{0, startNode});

        while (!pq.isEmpty()) {
            int[] polls = pq.poll();
            int cost = polls[0];
            int node = polls[1];

            for (int[] adjNodeCost : graph[node]) {
                int adjCost = adjNodeCost[0];
                int adjNode = adjNodeCost[1];

                if (adjCost + cost < distances[adjNode]) {
                    distances[adjNode] = adjCost + cost;
                    pq.add(new int[]{cost + adjCost, adjNode});
                }
            }
        }

        int item_count = 0;
        for (int i = 1; i < n + 1; i++) {
            if (distances[i] <= m) {
                item_count += items[i];
            }
        }
        max_item = Math.max(item_count, max_item);

    }
}

처음 문제를 제대로 읽지 않고 문제를 풀기 시작해서 다익스트라로 풀었다. 물론 각 노드에 대해 다익스트라를 반복해도되지만, 문제의 의도는 플로이드 와샬이었을 것이다.

내 풀이 - 파이썬

import sys
import copy
from collections import defaultdict
import heapq

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

items = list(map(int, input().split()))
graph = [[] for _ in range(n)]

answer = 0

def dijkstra(start_node):
    global answer
    distances = [sys.maxsize] * len(items)
    distances[start_node] = 0
    priority_queue = []
    heapq.heappush(priority_queue, (0, start_node))

    while priority_queue:
        cost, node = heapq.heappop(priority_queue)

        for adj_node_cost in graph[node]:
            adj_cost = adj_node_cost[0]
            adj_node = adj_node_cost[1]

            if adj_cost + cost < distances[adj_node]:
                distances[adj_node] = adj_cost + cost
                heapq.heappush(priority_queue, (cost + adj_cost, adj_node))

    item_count = 0
    for i in range(n):
        if distances[i] <= m:
            item_count += items[i]

    answer = max(answer, item_count)

for _ in range(r):
    a, b, l = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((l, b))
    graph[b].append((l, a))

    for i in range(len(items)):
        dijkstra(i)

print(answer)