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

 

문제 URL:

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

1325번: 효율적인 해킹

 

다음 문제는 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하는 문제로, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있게 된다.

 

이 문제는 한 컴퓨터가 해킹할 수 있는 컴퓨터 개수를 dfs방식을 이용하여 검사한 뒤,

각 컴퓨터의 해킹 가능 컴퓨터 개수를 비교하여 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호 출력한다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> vec[10001];	//이차원 벡터
bool visited[10001];	//방문 판단 배열
int hackingCNum = 0;	//해킹 가능한 컴퓨터 개수

void dfs(int node) {
	visited[node] = true;

	for (int newNode : vec[node])
		if (!visited[newNode]) {
			hackingCNum++;
			dfs(newNode);
		}
}

int main() {
	vector<int> answer;
	int n, m, a, b, maxCN = 1;
	cin >> n >> m;
	
	//b를 해킹하면, a도 해킹할 수 있기 때문에 B->A로 연결 리스트로 구현
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		vec[b].push_back(a);	//단방향 그래프
	}

	for (int i = 1; i <= n; i++) {	//노드 1부터 n까지 최대 해킹 컴퓨터 개수 검사
		fill_n(visited, sizeof(visited), false);	//배열 초기화
		hackingCNum = 0;
		dfs(i);

		if (hackingCNum > maxCN) {	//해당 노드의 해킹 가능한 컴퓨터 개수가 현재 max 값보다 크다면 answer에 값 추가
			answer.clear();
			answer.push_back(i);
			maxCN = hackingCNum;
		}
		else if(hackingCNum == maxCN)
			answer.push_back(i);
	}

	for (int n : answer)
		cout << n << " ";
}