[Algorithm] Baekjoon 1324번 : 효율적인 해킹

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
 
struct Node
{
    int num;
    int hackedComputerCount;
};
 
bool cmp(const Node& a, const Node& b)
{
    if (a.hackedComputerCount == b.hackedComputerCount)
    {
        return a.num < b.num;
    }
 
    return a.hackedComputerCount > b.hackedComputerCount;
}
 
int n, m, a, b;
vector<Node> hackedComputerCounts;
vector<vector<int>> graph(10001);
 
int BFS(int num)
{
    bool visited[10001] = { false };
    int count = 0;
    visited[num] = true;
    queue<int> q;
    q.push(num);
 
    while (!q.empty())
    {
        int curNode = q.front();
        q.pop();
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int child = graph[curNode][i];
 
            if (!visited[child])
            {
                visited[child] = true;
                ++count;
                q.push(child);
            }
        }
    }
    
    return count;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    hackedComputerCounts.resize(n + 1);
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
        
        graph[b].push_back(a);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        hackedComputerCounts[i] = { i, BFS(i) };
    }
 
    sort(hackedComputerCounts.begin(), hackedComputerCounts.end(), cmp);
 
    int standard = hackedComputerCounts[0].hackedComputerCount;
    printf("%d ", hackedComputerCounts[0].num);
 
    for (int i = 1; i < hackedComputerCounts.size(); ++i)
    {
        if (hackedComputerCounts[i].hackedComputerCount != standard)
        {
            break;
        }
 
        printf("%d ", hackedComputerCounts[i].num);
    }
}
 
 

 

싸이클없는문젠줄 알고 dp로 시도했었는데 시간초과로 틀렸다.

실버1문제치고 정답률이 18프로밖에 안돼서 '뭔 문제지?' 했는데, 약간 이해가 가는 문제였다.

 

일단 말해다시피 싸이클이 있는 문제이고, 그렇기때문에 내가 아는선에선 dp로는 못푼다. 

대신 이 문제가 실버인 이유가 있는데.. 시간제한이 5초이다.

 

그렇다. 그냥 노드마다 일일이 완탐으로 풀면된다..

물론 특정알고리즘같은걸 쓰면 매우 효율적으로 풀 수 있다고 한다. 

만약 이 문제의 시간제한이 5초가 아닌 1초라면 아마 이문제는 최소 골드2이상?의 문제일것이다.