[백준 문제 C++] 15591 MooTube (Silver)

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

15591번: MooTube (Silver)

 

문제를 간단하게 보면

1. 가중치가 있는 양방향 그래프를 입력 받습니다.

 ex) (예제 입력의 가중치 부분입니다.)

1 2 3
2 3 2
2 4 4

 

 

 

2. 시작 버텍스에서 k 가중치 이상인 곳만 탐색을 하고 갯수를 세면 됩니다.

 

 탐색은 DFS (Depth First Search : Stack)

             BFS (Breadth First Search : Queue)

 

둘 중에 어느 것을 사용하여도 상관없기에 재귀함수를 이용한 스택 방식으로 구현하였습니다.

 

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

vector<vector<pair<int, int>>> v;
vector<bool> visited;
int result;

void CheckLink(int k, int from)
{
	result++; //탐색마다 1씩 증가 시켜줍니다.
	visited[from] = true; //같은 인덱스 탐색을 막아줍니다.
	
	int size = v[from].size();

	for (int i = 0; i < size; ++i)
	{
		pair<int, int> p = v[from][i];
		int next = p.first;
		int cost = p.second;

		//이미 방문 되었거나 k보다 작은 곳은 갈 수 없습니다.
		if (visited[next] || cost < k)
		{
			continue;
		}

		//계속 탐색합니다.
		CheckLink(k, next);
	}
}

int main()
{
	int n, Q;
	int p, q, r;
	int k, from;

	scanf("%d %d", &n, &Q);

	v.resize(n + 1); //인덱스가 [1] ~ [n] 까지 시작하여 n + 1 만큼 사용합니다.
	visited.resize(n + 1, false);

	for (int i = 1; i < n; ++i) //n - 1개 입력이기에 i = 1부터 시작합니다.
	{
		scanf("%d %d %d", &p, &q, &r);

		//양방향 그래프이기에 서로 경로, 가중치 를 저장해줍니다.
		v[p].push_back(make_pair(q, r));
		v[q].push_back(make_pair(p, r));
	}

	for (int i = 0; i < Q; ++i)
	{
		scanf("%d %d", &k, &from);

		result = -1;

		//visited 배열을 false로 초기화 시켜줍니다.
		fill(visited.begin(), visited.end(), false);

		//DFS
		CheckLink(k, from);

		printf("%d\n", result);
	}
}