[ 백준 1325 ] 효율적인 해킹 (C++)

백준의 효율적인 해킹(1325) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 모든 컴퓨터를 시작점으로 해서, 신뢰하는 컴퓨터들을 타고 들어가면서 가장 많은 컴퓨터를 해킹할 때, 그 갯수를 출력하는

   DFS로 구현하는 문제이다.

   먼저 문제에 보면 "A가 B를 신뢰하는 경우, B를 해킹하면 A를 해킹할 수 있다" 라는 말이 있다.

   본인은 이 부분을 설정해주기 위해서 벡터를 하나 사용했으며, 각 컴퓨터마다 신뢰하는 컴퓨터들을 원소로 넣어주었다.

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        Computer[b].push_back(a);
        // a가 b를 신뢰한다.
        // 즉, b를 해킹하면 a도 해킹할 수 있다.
    }

  

2) DFS의 구현 방법은 어렵지 않다. 모든 컴퓨터들을 돌아보면서, 신뢰하는 컴퓨터가 있을 때 마다 해킹할 수 있는 컴퓨터의

   갯수를 ++ 시켜주면서, 최댓값을 갱신해 나가면 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
 
#define endl "\n"
#define MAX 10000 + 1
using namespace std;
 
int N, M, Num, Tmp_Answer;
bool Visit[MAX];
 
vector<int> Computer[MAX];
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        Computer[b].push_back(a);
        // a가 b를 신뢰한다.
        // 즉, b를 해킹하면 a도 해킹할 수 있다.
    }
}
 
void DFS(int x)
{
    Visit[x] = true;
 
    for (int i = 0; i < Computer[x].size(); i++)
    {
        int nx =  Computer[x][i];
        
        if (Visit[nx] == false)
        {
            Num++;
            DFS(nx);
        }
    }
    
}
 
void Solution()
{
    vector<int> Answer;
    for (int i = 1; i <= N; i++)
    {
        memset(Visit, false, sizeof(Visit));
        Num = 0;
        DFS(i);
 
        if (Tmp_Answer == Num)
        {
            Answer.push_back(i);
        }
        else if (Tmp_Answer < Num)
        {
            Tmp_Answer = Num;
            Answer.clear();
            Answer.push_back(i);
        }
    }
 
    sort(Answer.begin(), Answer.end());
    for (int i = 0; i < Answer.size(); i++)
    {
        cout << Answer[i] << " ";
    }
    cout << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}