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

백준 1325

🌲 문제 요약

어느 회사 컴퓨터의 신뢰 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 문제.

🌲 문제 풀이

벡터 adj에 신뢰 관계를 저장한 뒤, 각각의 해킹 가능한 컴퓨터의 개수를 배열 ret에 담는다. 이 과정에서 트리 탐색을 위하여, 함수 dfs를 재귀적으로 호출한다.

🌲 주의

컴퓨터의 해킹 정보를 ret에 담는 각각의 과정에 앞서, visited의 값을 0으로 초기화하도록 한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int n, m, mx, ret[10005], visited[10005];
vector<int> adj[10005];

int dfs(int here) {
	visited[here] = 1;
	int cnt = 1;
	for (int there : adj[here]) {
		if (visited[there]) continue;
		cnt += dfs(there);
	}
	return cnt;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		adj[tmp2].push_back(tmp1);
	}
	
	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		ret[i] = dfs(i);
		mx = max(mx, ret[i]);
	}
	
	for (int i = 1; i <= n; i++) {
		if (ret[i] == mx) cout << i << ' ';
	}
	cout << '\n';
	
	return 0;
}