[백준] 1325 효율적인 해킹

 

문제를 살펴보고 오자.

www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

문제를 읽어보면, 간단한 그래프 탐색 문제이다. A가 B를 신뢰하는 경우에 B를 해킹하면 A를 해킹할 수 있다는 말에서, 단방향 그래프 특성을 알 수 있다.

 

이를 이용해서 문제 풀이를 간단히 구상해보자. 노드의 개수(N)이 최대 만 개 이나 주어진 시간이 5초로 매우 넉넉하기 때문에, 마음에 드는 그래프 탐색 알고리즘을 하나 선택해서 구상해 보자. 나는 bfs 알고리즘을 사용했다.

 

모든 노드에 대해서 bfs를 돌린다. 임의의 시작 노드에 대하여 bfs를 돌린 결과값은 탐색한 노드의 수이다. queue에 숫자를 push 할 때 count 를 올려준다. 모든 결과에서 최댓값에 해당하는 시작 노드를 모두 출력하면 된다. 오름차순 출력이므로 간단히 구현이 가능하다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> v[10001];
 
int bfs(int start, int N)
{
    int ans = 0;
    int visited[10001] = {0};
    queue<int> q;
 
    q.push(start);
    visited[start] = 1;
    while(!q.empty())
    {
        int start = q.front();
        q.pop();
        for(auto i = v[start].begin(); i != v[start].end(); i++)
        {
            if (!visited[*i])
            {
                visited[*i] = 1;
                q.push(*i);
                ans++;
            }
        }
    }
    return (ans);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N, M, a, b, ans;
    int arr[10001];
 
    cin >> N >> M;
    while (M--)
    {
        cin >> a >> b;
        v[b].push_back(a);
    }
    ans = 0;
    for (int i = 1; i <= N; i++)
    {
        arr[i] = bfs(i, N);
        ans = max(ans, arr[i]);
    }
        
    for (int i = 1; i <= N; i++)
        if (ans == arr[i])
            cout << i << " ";
    return (0);
}

 

평범한 bfs를 사용했다. 코드를 줄일 수 있는 방법이 있으면 조금 더 찾아봐야 할 듯 하다.