코딩 테스트

프로그래머스 - 배달

N개의 노드를 연결하는 양방향 간선, 비용 존재
비용 K 이하로 이동이 가능한 노드의 갯수를 구해야 합니다.
시작 노드는 1로 고정인 것 같네요.
간선의 갯수가 N - 1이 아니고, 두 노드를 연결하는 간선이 여러개일 수 있습니다.
두 노드 A, B를 연결하는 노드 중 최소 비용의 노드만 남기고 나머지는 처내도 될 것 같네요.

실패 코드

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

using namespace std;

struct Node
{
    int start;
    int end;
    int cost;
};

void BFS(const vector<vector<int>>& graph, vector<int>& currentDist, int start,  int limitCost)
{
    queue<Node> q;
    for(int i = 0; i < currentDist.size(); i++)
    {
        if(currentDist[i] < limitCost)
        {
            Node node;
            node.start = start;
            node.end = i;
            node.cost = currentDist[i];
            q.push(node);
        }
    }
    
    while(!q.empty())
    {
        Node curNode = q.front();
        q.pop();
        
        int start = curNode.end;
        int curCost = curNode.cost;
        
        for(int i = 0; i < graph[start].size(); i++)
        {
            int end = i;
            int newCost = curCost + graph[start][i];
            
            if(newCost < currentDist[i])
            {
                currentDist[i] = newCost;
                Node newNode;
                newNode.start = start;
                newNode.end = end;
                newNode.cost = newCost;
                q.push(newNode);
            }
        }
    }
}
int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    vector<vector<int>> graph(N, vector<int>(N, K + 1));
    vector<int> minDists;
    
    for(vector<int> row : road)
    {
        int startNode = row[0] - 1;
        int endNode = row[1] - 1;
        int cost = row[2];
        int curCost = graph[startNode][endNode];
        
        if(curCost > cost)
        {
            graph[startNode][endNode] = cost;
            graph[endNode][startNode] = cost;
        }
    }
    
    for(int cost : graph[0])
    {
        minDists.push_back(cost);
    }
    
    BFS(graph, minDists, 0, K);
    
    for(int dist : minDists)
    {
        if(dist <= K)
        {
            answer++;
        }
    }
    return answer;
}

정답률은 87.5%였습니다.