[Algorithm]Baekjoon 14938번 :: 서강그라운드

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

14938번: 서강그라운드

 

#define MAX_NUM 0x3f3f3f3f
 
struct Node
{
    int node;
    int remainingDistance; // 잔여 거리 저장.
};
 
int items[101]; // 0 -> 0번째 노드가 가지고있는 아이템 수.
int adjMatrix[101][101] = { 0 };
int n, m, r, a, b, l;
bool visited[101];
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> r;
 
    memset(adjMatrix, 0x3f, sizeof(adjMatrix));
 
    for (int i = 1; i <= n; i++) // 각 구역의 아이템 수
    {
        cin >> items[i];
        adjMatrix[i][i] = 0;
    }
 
    for (int i = 0; i < r; i++)
    {
        cin >> a >> b >> l;
 
        adjMatrix[a][b] = l;
        adjMatrix[b][a] = l;
    }
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            if (adjMatrix[i][k] != MAX_NUM)
            {
              for (int j = 1; j <= n; j++)
            {
                if (adjMatrix[i][k] + adjMatrix[k][j] < adjMatrix[i][j])
                {
                    adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                }
            }
            }
        }
    }
 
    int result = 0;
 
    for (int i = 1; i <= n; i++)
    {
        int temp = 0;
 
        for (int j = 1; j <= n; j++)
        {
            if (adjMatrix[i][j] <= m)
            {
                temp += items[j];
            }
        }
 
        result = max(result, temp);
        int asdf = 0;
    }
 
 
    cout << result;
}

이 문제에서는 딱 한가지만 명심해야할 것은, 기준점으로 잡은 노드에서의 다른 노드까지의 거리가 인풋으로 주어지는 값 그대로가 아니라는 것이다.

인풋으로 1 5 7    이렇게 주어졌을 때, 1번에서 5번노드까지의 거리가 7이라는 뜻인데 이건 더 짧게 갱신될 여지가 있기 때문에 다익스트라나 플로이드와샬을 이용해서 각 노드까지의 값을 업데이트 해줘야 한다.

 

이 문제같은 경우는 모든 노드에 대해서 다 검사를 해야하기 때문에 그냥 플로이드와샬로 푸는게 제일 깔끔하다.

다익스트라는 한번 돌릴때마다 하나의 노드에대해서 다른 모든 노드까지의 최단거리가 업데이트 되고, 플로이드 와샬은 그냥 모든 노드에 대해서 다른 모든 노드까지의 최단거리가 업데이트된다. 

그렇기 때문에 플로이드와샬로 푸는게 편하고 깔끔하다.

 

플로이드와샬로 각 노드에서 노드까지의 최단거리를 모두 업데이트 한 후, 각 노드를 기준으로 수색범위 이내의 노드의 아이템개수값을 갱신시킨 후, 최종 최대값을 출력해주면 된다.