문제설명

1번마을부터 n번마을까지 존재합니다.
그래프를 줄테니
1번 마을에서의 최단거리가 K이하인 마을의 개수를 구하세요

아이디어

다익스트라로 1:N path 길이를 구한다

여담

python으로 풀어봤다.. heapq와 리스트 초기화를 처음 써봤다...
c++의 priority_queue의 경우에는 compare 연산자를 정의하는 게 필요했는데 바로 쓸 수 있어서 좋았다.

코드 python

import heapq
def solution(N, road, K):
    answer = 0
    al = [[] for i in range(N+1)] # road를 adj list
    for i in range(len(road)):
        a,b,c = road[i]
        al[a].append([b,c])
        al[b].append([a,c])
    
    #다익스트라
    INF = 10000*50
    dist = [INF for i in range(N+1)]
    
    q= [(0,1)] #원소는(거리, 번호)
    # 다익스트라 알고리즘을 수행
    while q:
        # 가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기
        d ,cur = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if dist[cur] < d:
            continue
        dist[cur] = d
        
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in range(len(al[cur])):
            b,c=al[cur][i]
            if d+c<dist[b]:
                heapq.heappush(q,(d+c,b))
    for i in range(len(dist)):
        if(dist[i]<=K):
            answer+=1

    return answer

코드 c++

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

using namespace std;
int INF = 10000*50;//49개의 도로를 거칠 수 있음
int dist[51];
struct pos{//road도 나타낼 수 있으며 pq원소도 됨
    int n,d;
    pos(int nn,int dd){
        n =nn; d= dd;
    }
};
struct comp{
    bool operator()(pos &a, pos &b){
        return a.d>b.d;
    }
};

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    //road를 adjacent list로 변환해야댐
    for(int i = 0;i<51;i++){
        dist[i]=INF;
    }
    vector<pos> rl[51];
    for(int i = 0;i<road.size();i++){
        int a = road[i][0],b = road[i][1],c = road[i][2];
        rl[a].push_back(pos(b,c));
        rl[b].push_back(pos(a,c));
    }
    
    //pq를 사용한 다익
    priority_queue<pos,vector<pos>, comp> q;
    q.push(pos(1, 0));
    while(!q.empty()){
        pos cur =q.top();
        q.pop();
        if(cur.d>=dist[cur.n]){
            continue;
        }

        dist[cur.n] = cur.d;
        for(int i = 0;i<rl[cur.n].size();i++){
            pos r = rl[cur.n][i];//child road
            if(r.d+cur.d<dist[r.n]){
                pos child = pos(r.n,cur.d+r.d);
                q.push(child);
            }
        }
    }
    
    for(int i = 1;i<=N;i++){
        cout<<i<<" " <<dist[i]<<endl;
        if(dist[i]<=K){
            answer++;
            
        }
    }
    
    return answer;
}