문제 URL
https://school.programmers.co.kr/learn/courses/30/lessons/12978
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[문제 설명]
다음 문제는 마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을(간선을 통한 이동 시간이 K시간 이하)의 개수를 return 문제이다.


[문제 풀이]
문제는 다익스트라 알고리즘을 사용하여 풀 수 있는 문제였다.
우선순위 큐를 사용하여 현재 노드의 위치값과 이동거리를 삽입해 주고, while문을 통해 현재 위치와 연결된 모든 노드들과 거리를 비교해 준다. 이후 저장한 최소 누적 이동값들 중 K 이하의 개수만큼 answer을 증가시켜 주면 된다.
#include <vector>
#include <queue>
using namespace std;
vector<pair<int,int>> V[51]; // 마을의 양방향 간선 벡터
vector<int> Dist; // 각 마을의 최소 거리를 저장해 줄 벡터
void Dijkstra(int N) {
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, 1));
Dist[1] = 0;
while (pq.empty() == 0) {
int Cost = -pq.top().first;
int Cur = pq.top().second;
pq.pop();
for (int i = 0; i < V[Cur].size(); i++) {
int Next = V[Cur][i].first;
int nCost = V[Cur][i].second;
if (Dist[Next] > Cost + nCost) {
Dist[Next] = Cost + nCost;
pq.push(make_pair(-Dist[Next], Next));
}
}
}
}
int solution(int N, vector<vector<int> > road, int K) {
Dist.resize(N + 1, 1e9); // 벡터 resizing
for (int i = 0; i < road.size(); i++) { // 양방향 간선의 값 모두 저장
int N1 = road[i][0];
int N2 = road[i][1];
int Dist = road[i][2];
V[N1].push_back(make_pair(N2, Dist));
V[N2].push_back(make_pair(N1, Dist));
}
Dijkstra(N);
int answer = 0;
for (int i = 1; i <= N; i++) {
if (Dist[i] <= K)
answer++;
}
return answer;
}