백준 1325 효율적인 해킹 (c++) : 피너클

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

1325번: 효율적인 해킹

dfs문제다.

int n, m;
vector<int> v[10001];
bool visited[10001];

사용할 변수다.

v[5] = [1, 2, 3, 4]라면 5를 해킹했을때 1, 2, 3, 4도 해킹할수 있다는 뜻이다.

cin >> n >> m;
for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    v[b].push_back(a);
}
vector<int> ans;
int big = 0;

값을 입력받을때 b에 a를 집어넣는다.

ans에는 컴퓨터 번호가 들어갈것이다.

big은 현재 한번에 가장 많이 해킹할수있는 숫자다.

for (int i = 1; i <= n; i++) {
    memset(visited, false, sizeof(visited));
    visited[i] = true;
    int now = dfs(i);
    if (big == now) ans.push_back(i);
    else if (big < now) {
        big = now;
        ans.clear();
        ans.push_back(i);
    }
}

이제 n만큼 반복문을 돌린다.

visited를 초기화하고 visited[i]를 true로 바꾼뒤 now에 dfs(i)를 입력한다.

만약 big과 같다면 ans에 i를 넣어주고

만약 big보다 크다면 big을 now로 바꾼뒤 ans를 초기화하고 ans에 i값을 넣어준다.

for (int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';

마지막으로 ans안의 값들을 출력하면 된다.

int dfs(int now) {
	visited[now] = true;
	int ans = 1;
	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];
		if (!visited[next]) ans += dfs(next);
	}
	return ans;
}

dfs함수다. 현재 번호를 방문했다고 저장하고

현재 번호에서 갈수있는 컴퓨터중 방문하지 않은 컴퓨터에 방문한다. ans=1인 이유는 자기 자신을 포함하기 때문이다.

그후 ans을 반환한다.

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

using namespace std;

int n, m;
vector<int> v[10001];
bool visited[10001];

int dfs(int now) {
	visited[now] = true;
	int ans = 1;
	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];
		if (!visited[next]) ans += dfs(next);
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[b].push_back(a);
	}
	vector<int> ans;
	int big = 0;
	for (int i = 1; i <= n; i++) {
		memset(visited, false, sizeof(visited));
		visited[i] = true;
		int now = dfs(i);
		if (big == now) ans.push_back(i);
		else if (big < now) {
			big = now;
			ans.clear();
			ans.push_back(i);
		}
	}
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
}

전체코드다.