[백준] 14938 - 서강그라운드

1. 문제

14938번: 서강그라운드

2. 개요

n개의 지역과 r개의 도로로 이루어진 맵이 있다. 첫 시작점에서 최대 m만큼 떨어진 곳까지 수색하여 아이템을 최대한 얻으려고 한다.

이 때 얻을 수 있는 아이템의 최대 갯수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

플로이드 워셜로 각 구역에서 다른 구역까지의 거리를 구한다.

이후 각 구역을 시작점으로 하여 다른 모든 구역까지의 거리를 확인한다.

이 거리가 수색범위보다 작다면 그 구역의 아이템 수 만큼 늘려준다.

아이템 수가 최대가 되는 구역의 총 아이템 수를 답으로 출력한다.

3-2. Python

import sys

n, m, r = map(int, sys.stdin.readline().split())

maxvalue = 100000

graph = [[100000 for i in range(n)] for j in range(n)]

tems = list(map(int, sys.stdin.readline().split()))

for i in range(r):
    info = list(map(int, sys.stdin.readline().split()))

    graph[info[0] - 1][info[1] - 1] = info[2]
    graph[info[1] - 1][info[0] - 1] = info[2]

for i in range(n):
    graph[i][i] = 0

for k in range(n):
    for s in range(n):
        for e in range(n):
            if graph[s][e] > graph[s][k] + graph[k][e]:
                graph[s][e] = graph[s][k] + graph[k][e]

answer = 0

for i in range(n):
    tmp = 0
    for j in range(n):
        if graph[i][j] <= m:
            tmp += tems[j]

    if tmp > answer:
        answer = tmp

print(answer)

3-3. C#

namespace boj_14938
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);
            int R = int.Parse(input[2]);

            int maxvalue = 100000;

            List<List<int>> graph = new List<List<int>>();

            for (int i = 0; i < N; i++)
            {
                graph.Add(Enumerable.Repeat(maxvalue, N).ToList());
                graph[i][i] = 0;
            }

            int[] tems = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

            for (int i = 0; i < R; i++)
            {
                string[] info = sr.ReadLine().Split();

                int a = int.Parse(info[0]);
                int b = int.Parse(info[1]);
                int c = int.Parse(info[2]);

                graph[a - 1][b - 1] = c;
                graph[b - 1][a - 1] = c;
            }

            for (int m = 0; m < N; m++)
            {
                for (int s = 0; s < N; s++)
                {
                    for (int e = 0; e < N; e++)
                    {
                        if (graph[s][e] > graph[s][m] + graph[m][e])
                            graph[s][e] = graph[s][m] + graph[m][e];
                    }
                }
            }

            int answer = 0;
            int tmp = 0;

            for (int i = 0; i < N; i++)
            {
                tmp = 0;
                for (int j = 0; j < N; j++)
                {
                    if (graph[i][j] <= M)
                        tmp += tems[j];
                }

                if (tmp > answer)
                    answer = tmp;
            }

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}