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

문제

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

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

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

입력

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

출력

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

구현해야 할 조건

입력 조건이 10,000이기 때문에, 단순한 배열로 검색을 하기에는 엄청난 시간이 걸린다. c++에는 막강한 vector가 있기 때문에 vector로 들어간 녀석들만 검색을 해서 DFS를 통해 탐색을 해보자!

code

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

#define MAX 10001
using namespace std;

int n,m,cnt;
bool visited[MAX];
vector<int> board[MAX];

void DFS(int node)
{
	visited[node] = true; // visited 체크 다신 돌아오지 못하게
	
	for(int i = 0; i < board[node].size(); i++){
		int next = board[node][i]; // 다음 next는 누구?
		
		if(!visited[next]) // 방문된적 없으면
		{
			cnt++; // cnt++추가
			DFS(next); // 다시 돌리자
		}	
	}
}

int main()
{
	memset(board,0,sizeof(board));
	
	cin >> n >> m;
	
	for(int i = 0; i < m; i++)
	{
		int a,b;
		cin >> a >> b; 
		board[b].push_back(a); // 신뢰하고 있는 관계를 vector board에 넣어줍니다.
	}
	
	int nodeCnt = 0;
	
	vector<int> res;
	
	for(int i = 1; i <= n; i++){
		memset(visited,0,sizeof(visited)); // visited를 계속 초기화 1~n 까지 몇개를 감염하는지 체크해야하기 때문에
		cnt = 0;
		DFS(i); // DFS를 돌립니다.
		
		
		if(nodeCnt == cnt)
			res.push_back(i); // 최대 갯수랑 같으면? 일단 넣어줘
			
		if(nodeCnt < cnt) // cnt가 크다면?
		{
			nodeCnt = cnt; // update한 후
			res.clear(); // 이제까지 들어가있던 애들 다 삭제
			res.push_back(i); // number 넣어주기
		}
	}
	
	sort(res.begin(), res.end()); // 삭 정렬해주고
	
	for(int i = 0; i < res.size(); i++)
		cout << res[i] << " "; // 뽑아내기!
	
	
	
	return 0;
}