https://school.programmers.co.kr/learn/courses/30/lessons/132266
λ¬Έμ μ€λͺ
κ°μ² λΆλμ κ° λΆλμμ΄ μ¬λ¬ μ§μμ λΏλΏμ΄ ν©μ΄μ Έ νΉμ μ무λ₯Ό μν μ€μ λλ€. μ§λμμ κ°μ² λΆλκ° μμΉν μ§μμ ν¬ν¨ν κ° μ§μμ μ μΌν λ²νΈλ‘ ꡬλΆλλ©°, λ μ§μ κ°μ κΈΈμ ν΅κ³Όνλ λ° κ±Έλ¦¬λ μκ°μ λͺ¨λ 1λ‘ λμΌν©λλ€. μ무λ₯Ό μνν κ° λΆλμμ μ§λ μ 보λ₯Ό μ΄μ©νμ¬ μ΅λ¨μκ°μ λΆλλ‘ λ³΅κ·νκ³ μ ν©λλ€. λ€λ§ μ κ΅°μ λ°©ν΄λ‘ μΈν΄, μ무μ μμ λμ λ€λ₯΄κ² λλμμ€λ κ²½λ‘κ° μμ΄μ Έ 볡κ·κ° λΆκ°λ₯ν λΆλμλ μμ μ μμ΅λλ€.
κ°μ² λΆλκ° μμΉν μ§μμ ν¬ν¨ν μ΄μ§μμ μ n, λ μ§μμ μ볡ν μ μλ κΈΈ μ 보λ₯Ό λ΄μ 2μ°¨μ μ μ λ°°μ΄ roads, κ° λΆλμμ΄ μμΉν μλ‘ λ€λ₯Έ μ§μλ€μ λνλ΄λ μ μ λ°°μ΄ sources, κ°μ² λΆλμ μ§μ destinationμ΄ μ£Όμ΄μ‘μ λ, μ£Όμ΄μ§ sourcesμ μμ μμλλ‘ κ°μ² λΆλλ‘ λ³΅κ·ν μ μλ μ΅λ¨μκ°μ λ΄μ λ°°μ΄μ returnνλ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ. 볡κ·κ° λΆκ°λ₯ν κ²½μ° ν΄λΉ λΆλμμ μ΅λ¨μκ°μ -1μ λλ€.
λ΄ νμ΄
λ€μ΅μ€νΈλΌ μκ³ λ¦¬μ¦μ μ¬μ©ν΄ λͺ©μ μ§(destination)λΆν° λͺ¨λ μ§μ κΉμ§μ 거리λ₯Ό ꡬν λ€ μ‘°κ±΄μ λ§κ² λ°νν΄μ£Όλ©΄ λλ€.
#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
vector<int> answer;
vector<vector<int>> map(n);
int max_int = 999'999;
vector<int> distance(n, max_int);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
for(const auto& r : roads)
{
map[r[0]-1].push_back(r[1]-1);
map[r[1]-1].push_back(r[0]-1);
}
// λͺ©μ μ§λ₯Ό νμ μΆκ°
pq.push({0, destination-1});
while(!pq.empty())
{
auto top = pq.top();
pq.pop();
int r = top.second;
int d = top.first;
distance[r] = min(distance[r], d);
for(int i = 0; i < map[r].size(); ++i)
{
int nxt = map[r][i];
int dist = d + 1;
if(dist < distance[nxt])
{
pq.push({dist, nxt});
}
}
}
for(int s : sources)
{
if(max_int != distance[s-1])
answer.push_back(distance[s-1]);
else
answer.push_back(-1);
}
return answer;
}
μ±μ κ²°κ³Ό
'π₯οΈ Study Note > Coding Test' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Hacker Rank] Organizing Containers of Balls (C++) (1) | 2023.10.09 |
---|---|
[νλ‘κ·Έλλ¨Έμ€]level.3 - μΉ΄λ μ§ λ§μΆκΈ°(C++) (1) | 2023.10.05 |
[νλ‘κ·Έλλ¨Έμ€]level.2 - κ°μ₯ ν° μ μ¬κ°ν μ°ΎκΈ°(C++) (0) | 2023.09.28 |
[νλ‘κ·Έλλ¨Έμ€]level.3 - λ€λ¨κ³ μΉ«μ ν맀 (C++) (0) | 2023.09.26 |
[νλ‘κ·Έλλ¨Έμ€]level.2 - μ«μ λ³ννκΈ° (C++) (0) | 2023.09.22 |