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

15591. MooTube (Silver)

15591번: MooTube (Silver)

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

유사도란 말에 겁먹었지만... 사실은 가중치라고 표현해도 무방할 정도였다.

또 겁먹은 것은,

존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.

이 최솟값이라는 말이었다.

문제가 감이 안 와서, 예제를 분석해보았다.

 

 예제는 조건이 딸린 흔한 BFS 탐색이라서  불안하지만 저 조건을 제외하고 풀었다.

스패닝 트리를 탐색하고, 조건에 맞지 않는다면 탐색을 즉시 중단하는 문제이므로 BFS로 구현해 조건에 맞지 않는다면 queue에 노드를 넣지 않는다는 아이디어로 출발했다.

알고리즘 설계

1. 2개의 노드와 유사도를 입력받고 서로가 연결되어있는 노드임을 체크한다 (삽입).
2. Q번 BFS 탐색을 한다.
3. BFS 탐색을 하는 동안, Enque할 때마다 카운트를 하나씩 세준다.
4. 탐색이 끝난 다음에 카운트를 출력한다.

문제가 장황하고 긴 것에 비해서 기본적인 탐색이라 진이 빠졌다...

코드

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;

struct node
{
    int a; ull w;
};

// index에 연결된 노드를 모아놓는 변수
vector<node> arr[5001];

int main()
{
    int vCnt, lCnt;
    cin >> vCnt >> lCnt;

    for (int i = 0; i < vCnt - 1; i++)
    {
        int a, b;
        ull w;
        cin >> a >> b >> w;

        // 양방향 간선
        arr[a].push_back({ b,w });
        arr[b].push_back({ a,w });
    }

    for (int i = 0; i < lCnt; i++)
    {
        // BFS
        bool visited[5001];
        fill_n(visited, 5001, false);

        queue<int> q;
        int target, count = 0;
        ull usado;

        // 처음 탐색할 노드를 queue에 넣는다
        cin >> usado >> target;
        q.push(target);

        // queue가 빌 때까지
        while (!q.empty())
        {
            int node = q.front();
            q.pop();

            // 탐색하지 않은 곳이라면 => 탐색
            if (!visited[node])
            {
                visited[node] = true; // 방문했음을 체크

                // 인접한 노드들을 모두 탐색
                for (int j = 0; j < arr[node].size(); j++)
                {
                    if (arr[node][j].w >= usado)
                    {
                        int n = arr[node][j].a;

                        // 방문하지 않았다면 enque & count++
                        if (!visited[n])
                        {
                            q.push(n);
                            count++;
                        }
                    }
                }
            }
        }

        cout << count << endl;
    }
}

아 맞다. 앞으로 문제를 풀고 푼 코드의 시간 복잡도를 써보려고 한다. 많은 문제의 시간을 줄이는 데 도움이 될 것 같아서...

이 코드의 시간 복잡도는 Q개의 테스트케이스 + 인접 행렬로 구현한 BFS이므로...

O(Q*N)이다.

 

앞으로 시간 복잡도를 쓰는 걸 습관 들여야지!!