개요

백준 1325 (효율적인 해킹)

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

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

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

접근 방식

1. 이차원 벡터를 이용해 노드들을 트리로 엮어줬다.

2. DFS를 이용해 해당 컴퍼넌트에 포함되는 지 검사를 했다.

3. 다른 컴퍼넌트일 수 도 있으므로 각 노드에 대해 DFS를 해줬다.

전체 코드

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

vector<int> v[10'000];
bool visited[10'001];
vector<int> maxNumArr;
int GetComponentSize(int N) {
	visited[N] = true;
	int sum = 1;
	for (int elem : v[N])
		if(!visited[elem])
		sum += GetComponentSize(elem);
	return sum;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int N, M, trusting,trusted;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> trusting >> trusted;
	v[trusted].push_back(trusting);
	}
	int maxNum=0,tmpComponentSize=0;
	for (int i = 1; i <= N; i++) {
		fill(&visited[0], &visited[N+1], false);

		tmpComponentSize = GetComponentSize(i);
		if (maxNum < tmpComponentSize) {
			maxNumArr.clear();
			maxNumArr.push_back(i);
			maxNum = tmpComponentSize;
		}
		else if (maxNum == tmpComponentSize)
			maxNumArr.push_back(i);
		else 
			continue;
	}
	sort(maxNumArr.begin(), maxNumArr.end());
	for (int elem : maxNumArr)
		cout << elem<<" ";
}

생각

다른 컴퍼넌트에 존재할 수 있다도 중요한 포인트고,
각 배열마다 방문 여부 배열 초기화해야한다도 중요한 포인트다.