๐ฃ ๋ฌธ์ ์ดํด
ํ ์ถ๋ฐ ์ ์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ์ผ๋ก์ ์ต๋จ ๊ฒฝ๋ก ์ด๋ ๋น์ฉ์ ๊ณ์ฐํ๋ ๋ฌธ์ ์๋ค.
๊ฐ ๋ ธ๋๋ก ์ด๋ํ๋ ์ต์ ๋น์ฉ์ ๊ณ์ฐํ์ฌ ๊ทธ์ค ์ต๋๋ฅผ ๊ตฌํ ํ,
๋์ผํ ๋น์ฉ์ ์ง๋ถํ๋ ๊ฒฝ๋ก์ ์๋ฅผ ์นด์ดํธ ํ๋ค.
์ด ๋ฌธ์ ๋ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ดํ๋ค.
๐ญ ํ์ด ๊ณผ์
์์ฑ ์ธ์ด: C++
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 20001;
const int INF = 1e9;
int dist[MAX] = {0, };
int solution(int n, vector<vector<int>> edge) {
int max_cost = 0;
int result = 0;
priority_queue<pair<int, int>>pq; // ๋น์ฉ, ๋
ธ๋๋ฒํธ
vector<int>nodes[n+1];
// ๊ฐ ๋
ธ๋๊น์ง ๋๋ฌํ๋๋ฐ ์ต์ ๋น์ฉ(ํฐ ๊ฐ์ผ๋ก ์ค์ )
fill_n(dist, MAX, INF);
// ๋
ธ๋ ๊ธฐ์ค์ผ๋ก ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋๋ค์ ์ ๋ณด๋ฅผ ํ๊ธฐ
for (int i = 0; i < edge.size(); ++i) {
int vertex_a = edge[i][0];
int vertex_b = edge[i][1];
nodes[vertex_a].push_back(vertex_b);
nodes[vertex_b].push_back(vertex_a);
}
pq.push({0, 1});
// ์ฐ์ ์์ ํ ๋ด์์ ๊ฐ์ฅ ์์ ๊ฐ์ ๋จผ์ ๋ฐํํ ๊ฒ.
// ์ฐ์ ์์ ํ๋ ์ต๋ ํ์ ์ฌ์ฉํ๋ฏ๋ก cost๋ฅผ ์์ํํด์ ์ต์ ํ์ผ๋ก ์ฌ์ฉ.
while (!pq.empty()) {
int cur_cost = pq.top().first * -1;
int cur_node = pq.top().second;
pq.pop();
for (int i = 0; i < nodes[cur_node].size(); ++i) {
int next_node = nodes[cur_node][i];
if (dist[next_node] <= cur_cost + 1) continue;
dist[next_node] = cur_cost + 1;
pq.push({dist[next_node]*-1, next_node});
}
}
max_cost = *max_element(dist+2, dist+n);
for (int i = 2; i <= n; ++i) {
if (dist[i] == max_cost) result++;
}
return result;
}
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์์
์ ์ ๊ฐ์๊ฐ V์ด๊ณ ๊ฐ์ ๊ฐฏ์๊ฐ E์ผ ๋ ์ผ๋ฐ์ ์ธ ๋ฐฉ์์ผ๋ก๋ ์๊ฐ ๋ณต์ก๋๊ฐ O(V^2)๊ฐ ๋๋ฉฐ,
์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋ค๋ฉด Heap์ ์ฌ์ฉํ์ฌ ์๊ฐ๋ณต์ก๋๊ฐ O(ElogV)๊ฐ ๋๋ค.
์ฆ, ๋ ธ๋์ ์๊ฐ ๋ง์์ง๋ฉด ๋ง์์ง์๋ก, ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด ๋งค์ฐ ํจ๊ณผ์ ์ด๋ค.