Programmers - 배달

---

title: Programmers - 배달
date: 2022-06-21
tags:

• Algorithm
• Graph
• Dijkstra

---

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

문제 요약

주어진 그래프에서 root 노드로부터 K 가중치 내로 이동 가능한 노드의 수를 구하여 return한다.

문제 풀이

전형적인 Dijkstra Graph 문제이다.
주어진 그래프를 인접행렬로 변환한 후, N-1번 거리를 갱신하여 root로부터 모든 노드로 가는 거리가 K 이하인 노드의 개수를 구한다.
갱신이 이루어지지 않을 때 갱신을 중단하여도 되지만, 최대 갱신 횟수는 N-1번이다. 중단 조건 구현이 귀찮아서 N-1번 갱신하였다.
가중치에 -가 존재한다면 Floyd-Warshall 알고리즘을 사용하여야 한다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;

int solution ( int N , vector < vector < int > > road , int K )
{
    int idrgPath [ 50 ] [ 50 ] = { 0 , } ;
    bool brgVisit [ 50 ] = { false , } ;
    int iEnd = 0 ;
    int iWeight = 0 ;
    int iAnswer = 1 ;



    std :: fill ( idrgPath [ 0 ] , idrgPath [ 0 ] + 2500 , 1e6 ) ;            // For impossible node, fill with 1e6 > ( 50 * 1e4 )

    for ( int i = 0 ; i < road.size () ; ++ i )                // Initialize
    {
        int * ipTemp = road [ i ].data () ;
        int iStart = ipTemp [ 0 ] - 1 ;
        iEnd = ipTemp [ 1 ] - 1 ;
        iWeight = ipTemp [ 2 ] ;


        idrgPath [ iStart ] [ iEnd ] = std :: min ( idrgPath [ iStart ] [ iEnd ] , iWeight ) ;
        idrgPath [ iEnd ] [ iStart ] = std :: min ( idrgPath [ iEnd ] [ iStart ] , iWeight ) ;
    }

    brgVisit [ 0 ] = true ;

    for ( int i = 0 ; i < 49 ; ++i )                                    // Need to compute n - 1
    {
        iWeight = 1e6 ;

        for ( int j = 1 ; j < 50 ; ++j )                                // Find minimal path
        {
            if ( ( ! brgVisit [ j ] ) && ( idrgPath [ 0 ] [ j ] < iWeight ) )
            {
                iWeight = idrgPath [ 0 ] [ j ] ;
                iEnd = j ; 
            }
        }

        brgVisit [ iEnd ] = true ;
        for ( int j = 1 ; j < 50 ; ++j )                                // Update
        {
            idrgPath [ 0 ] [ j ] = std :: min ( idrgPath [ 0 ] [ j ] , idrgPath [ 0 ] [ iEnd ] + idrgPath [ iEnd ] [ j ] ) ;
        }
    }

    for ( int i = 1 ; i < 50 ; ++i )
    {
        if ( idrgPath [ 0 ] [ i ] <= K )
            ++ iAnswer ;
    }

    return iAnswer ;
}