백준 1325 c++ "효율적인 해킹" -PlusUltraCode-

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

 

 

 

 

 

[필자 사고]

문제를 살펴보면 A가 B를 신뢰할 경우 B를 해킹시 A또한 해킹 가능하다고 적혀있다.

 

A -> B 와 같은 형태로 단반향 그래프를 그려볼 수 있다.

 

모든 구간에서 BFS탐색을 통해 방문한 곳을 1씩 증가시키면 어떤 컴퓨터를 해킹시 몇개를 추가적으로 해킹할지 알 수 있게 된다.

 

주의할 점은 매번 BFS돌릴 때 마다 visted 배열을 초기화 시켜줘야 된다.

 

 

[소스 코드]

 

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

using namespace std;

int N, M;
vector<vector<int>> arr;


void Input() {
	cin >> N >> M;
	arr.resize(N + 1);
	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		arr[start].push_back(end);
	}
}

vector<bool> cVisited;
vector<int> resultCount;

void BFS(int startIdx, vector<bool>& visited) {
	queue<int> myQueue;
	myQueue.push(startIdx);
	visited[startIdx] = true;
	
	while (!myQueue.empty()) {
		int nowIdx = myQueue.front();
		myQueue.pop();

		for (int nextIdx : arr[nowIdx]) {
			if (visited[nextIdx] == false) {
				resultCount[nextIdx]++;
				visited[nextIdx] = true;
				myQueue.push(nextIdx);
			}
		}
	}
}

void GameStart() {
	cVisited.resize(N+1,false);
	resultCount.resize(N + 1, 0);
	
	for (int i = 1; i <= N; i++) {
		vector<bool> visited = cVisited;
		BFS(i, visited);
	}

	int maxCount = *max_element(resultCount.begin(), resultCount.end());

	for (int i = 1; i <= N; i++) {
		if (resultCount[i] == maxCount) {
			cout << i << " ";
		}
	}

}


int main(void) {
	Input();
	GameStart();
}