프로그래머스 - 배달 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

#include <iostream>
#include <vector>
using namespace std;

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;

    vector<vector<int>> dist(N+1,vector<int>(N+1,1e9));
    
    for(auto& item :road)
    {
        if(dist[item[0]][item[1]]!=1e9)
        {
            if(dist[item[0]][item[1]]>item[2])
            {
                dist[item[0]][item[1]]=item[2];
                dist[item[1]][item[0]]=item[2];
            }
        }
        else
        {
            dist[item[0]][item[1]]=item[2];
            dist[item[1]][item[0]]=item[2];
        }
    }
    for(int i=1;i<=N;i++)
        dist[i][i]=0;
    
    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                if(dist[i][j]>dist[i][k]+dist[k][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
    
    for(int i=1;i<=N;i++)
        if(dist[1][i]<=K)
            answer++;

    return answer;
}

주어진 그래프정보를 바탕으로 1번과의 거리가 K 이하인 노드의 개수를 리턴하는 문제이다. 

 

그래프의 모든 경로의 최단경로를 구하느 플로이드-워셜 알고리즘을 사용하여 푼다. 

 

vector<vector<int>> dist(N+1,vector<int>(N+1,1e9));
    
    for(auto& item :road)
    {
        if(dist[item[0]][item[1]]!=1e9)
        {
            if(dist[item[0]][item[1]]>item[2])
            {
                dist[item[0]][item[1]]=item[2];
                dist[item[1]][item[0]]=item[2];
            }
        }
        else
        {
            dist[item[0]][item[1]]=item[2];
            dist[item[1]][item[0]]=item[2];
        }
    }
    for(int i=1;i<=N;i++)
        dist[i][i]=0;

i -> j 경로에 대해서 여러 정보가 들어올 수 있기 때문에 그 중 최소값을 적용해야 한다. 

 

그리고 i->i는 0으로 초기화한다. 

 

for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                if(dist[i][j]>dist[i][k]+dist[k][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
    
    for(int i=1;i<=N;i++)
        if(dist[1][i]<=K)
            answer++;

알고리즘을 실행 후, k보다 작으면 answer를 카운트한다.