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

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

1325번: 효율적인 해킹

개인적으로 왜 정답률이 낮은지 알 수 없는 문제였다. 문제를 해결하는 포인트는 첫번째 인접리스트를 만들어 DFS를 진행하는 것이다. 두번째, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 여러 개 출력해야하므로, 가장 많은 컴퓨터를 해킹할 수 있는 경우가 갱신되면 벡터를 초기화하고 현재 컴퓨터 번호를 넣어줘야 한다. 그리고 만약 컴퓨터를 해킹할 수 있는 수가 같다면 현재 벡터에 현재 컴퓨터 번호를 추가해준다.

 

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

int N, M, maxx = INT_MIN;
vector<int> graph[10001], res;
bool visit[10001];

int getCnt(int now) {
	int cnt = 0;
	for(int i = 1; i <= N; i++) {
		if(now == i) continue;
		if(visit[i]) cnt++; 
	}
	return cnt;
}

void DFS(int node) {
	for(int i = 0; i < graph[node].size(); i++) {
		int next = graph[node][i];
		if(!visit[next]) {
			visit[next] = true;
			DFS(next);
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
		
	cin >> N >> M;
	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		graph[b].push_back(a);
	}
	
	for(int i = 1; i <= N; i++) {
		visit[i] = true;
		DFS(i);
		int cnt = getCnt(i);
		if(maxx < cnt) {
			maxx = cnt;
			res.clear();
			res.push_back(i);
		} else if(maxx == cnt) {
			res.push_back(i);
		}
		memset(visit, false, sizeof(visit));
	}
	
	sort(res.begin(), res.end());
	
	for(int i = 0; i < res.size(); i++) {
		cout << res[i] << " ";
	}
}