[백준] 효율적인 해킹 c++

효율적인 해킹

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

5 초

256 MB

103530

15671

10554

18.872%

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

---

BFS를 이용해 문제를 해결

한번에 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호 = 탐색되는 노드가 많은 컴퓨터 번호

탐색을 수행하면서 각 컴퓨터가 얼만큼 탐색이 돼었는지 저장

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> A;
vector<int> Answer;
vector<bool> Visited;

void BFS(int node)
{
	queue<int> myQueue;
	myQueue.push(node);
	Visited[node] = true;

	while (false == myQueue.empty())
	{
		int now = myQueue.front();
		myQueue.pop();

		for (int i : A[now])
		{
			if (false == Visited[i])
			{
				Visited[i] = true;
				Answer[i]++;
				myQueue.push(i);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	A.resize(n + 1);
	Visited.resize(n + 1);
	Answer.resize(n + 1);

	for (int i = 0; i < m; i++)
	{
		int s, e;
		cin >> s >> e;
		A[s].push_back(e);
	}

	for (int i = 0; i <= n; i++)
	{
		fill(Visited.begin(), Visited.end(), false);
		BFS(i);
	}

	int maxVal = 0;

	for (int i = 0; i <= n; i++)
	{
		maxVal = max(maxVal, Answer[i]);
	}

	for (int i = 0; i <= n; i++)
	{
		if (Answer[i] == maxVal)
		{
			cout << i << " ";
		}
	}
}

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