[ 프로그래머스 ] 배달

문제

---

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

풀이

---

마을 간 연결 정보와 거리를 입력 받아 1번 마을과 k이하의 거리를 가진 마을들을 찾는 문제이다. 다익스트라 알고리즘을 토대로 마을 별 최소 거리를 측정, k이하의 거리를 가진 마을의 개수를 return한다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct EDGE
{
    int adj;
    int w;
};

int solution(int N, vector<vector<int>> road, int K)
{
    vector<vector<EDGE>> graph(N + 2);
    int answer = 1;

    for (int i = 0; i < road.size(); i++)
    {
        graph[road[i][0]].push_back({ road[i][1],road[i][2] });
        graph[road[i][1]].push_back({ road[i][0],road[i][2] });
    }

    vector <int> strength(N + 2);
    queue<int>q;
    q.push(1);

    while (!q.empty())
    {
        int current = q.front();
        q.pop();

        for (int i = 0; i < graph[current].size(); i++)
        {
            int current_strength = strength[current] + graph[current][i].w;

            if (strength[graph[current][i].adj] == 0)
            {
                strength[graph[current][i].adj] = current_strength;
                q.push(graph[current][i].adj);
            }

            else  if (strength[graph[current][i].adj] > current_strength)
            {
                strength[graph[current][i].adj] = current_strength;
                q.push(graph[current][i].adj);
            }

        }

    }

    for (int i = 2; i < strength.size(); i++)
    {
        if (strength[i] != 0 && strength[i] <= K)
        {
            answer++;
        }
    }

    return answer;
}