BeakJoon 15591 MooTube (Silver)

안녕하세요. 이번 포스팅에서는 백준 15591번 MooTube 문제를 풀어보도록 하겠습니다.

 

https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

 

해당 문제는 위 링크를 통해 확인하실 수 있습니다.

 

너무 쉽게 생각했다가... 낭패 본 문제입니다.

 

우선 그래프에 가중치가 존재해서, 당연히 다익스트라이겠거니 했는데, 그냥 BFS탐색으로 구현하시면 됩니다.

 

구현 로직은

 

시작점 출발 -> 연결된 노드중에 거리의 값이 더 작은 노드 && 방문하지 않은 노드가 있다면 거리 값 저장 후 큐에 추가

-> q가 빌때 까지 계속 반복하며 거리 값 갱신

 

BFS를 순회하며 계속 최소인 거리 값을 경신해 나가면서 저장해주시면 됩니다.

해주시면 됩니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, q;
vector<pair<ll, ll>> graph[5004];
ll dist[5004];
bool visited[5004];
void search(int start) {
	queue<pair<ll, ll>> q;
	fill(dist, dist+5004, 1e10);
	fill(visited, visited+5004, 0);
	dist[start] = 1e10;
	visited[start] = 1;
	q.push({1e10, start});
	
	while(!q.empty()) {
		pair<ll, ll> cur = q.front(); q.pop();
		ll curNode = cur.second;
		ll curDist = cur.first;
		
		for(int i = 0; i < graph[curNode].size(); i++) {
			ll nextDist = min(curDist, graph[curNode][i].second);
			ll nextNode = graph[curNode][i].first;
			if(visited[nextNode]) continue;
			visited[nextNode] = 1;
			if(dist[nextNode] > nextDist) {
				dist[nextNode] = nextDist;
				q.push({nextDist, nextNode});
			} 
		}
	}
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> q;
	for(int i = 1; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		graph[a].push_back({b,c});
		graph[b].push_back({a,c});
	} 
	
	for(int i = 0; i < q; i++) {
		ll a, b; cin >> a >> b;
		ll ret = 0;
		search(b);
		for(int i = 1; i <= n; i++) if(dist[i] != 1e10 && dist[i] >= a) ret++;
		cout << ret << "\n";
	}	
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.