[Algorithm] Baekjoon 15591번 : MooTube

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

15591번: MooTube (Silver)

 

struct Node
{
    int node;
    int weight;
};
 
vector<vector<Node>> graph(5001);
 
int answer = 0;
bool visited[5001];
 
void DFS(int index, int k)
{
 
    for (int i = 0; i < graph[index].size(); ++i)
    {
        int curNode = graph[index][i].node;
        int curWeight = graph[index][i].weight;
 
        if (curWeight >= k && !visited[curNode])
        {
            visited[curNode] = true;
            ++answer;
            DFS(curNode, k);
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, q, a, b, c;
 
    cin >> n >> q;
 
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b >> c;
        graph[a].push_back({ b,c });
        graph[b].push_back({ a,c });
    }
    
    for (int i = 0; i < q; ++i)
    {
        cin >> a >> b;
        answer = 0;
        memset(visited, false, sizeof(visited));
        visited[b] = true;
 
        DFS(b, a);
        printf("%d\n", answer);
    }
}

 

 

뭔가 문제설명은 복잡하게 되어있긴한데, 테스트케이스밑에 해설보면 쉽게 이해 가능하다.

사실 설명을 아예 안보는게 나을정도;

일단 주어진 간선정보로 각 노드를 양방향으로 연결해서 그래프를 만든다.

그다음 k와 정점이 주어지는데, 해당 정점을 시작으로 뻗어나가면서 k이상인 정점들을 카운팅해주기만 하면 된다.

도중에 k이하인곳에서는 뻗어나가는것만 멈춰주자.

가중치 최대값은 10억이긴한데 어차피 누적합 할것도 아니라서 그냥 int로 해도된다.