C++ 1325 효율적인 해킹

백준 1325 

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

1325번: 효율적인 해킹

풀이 전 나의 생각

회사 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를

해킹할 수 있는 컴퓨터의 번호를 구해야 한다.

 

조건

- N은 10,000보다 작거나 같은 자연수

- M은 100,000보다 작거나 같은 자연수

 

과정

다른 문제보다 유난히 주어지는 관계의 수가 많지만 시간 제한이 5초기 때문에

평범한 DFS, BFS탐색을 이용하여 풀 수 있다.

 

여기서 중요한 것은 A가 B를 신뢰하는 경우, B가 A를 공격할 수 있다는 부분이다.

생각없이 A -> B의 형태로 관계 정보를 저장하면 A가 B를 신뢰하며 A가 B를 공격하기

때문에 이를 유의하며 정보를 저장해야 한다.

 

두 번째로 A가 B를 신뢰한다고 했을 때, B도 A를 신뢰할 수 있다.

따라서 방향성이 있는 그래프지만 전의 노드를 재탐색할 경우를

대비해 방문 표시를 해줘야한다.

 

이러한 점을 생각하며

DFS, BFS를 이용한 탐색을 진행할 때 마다 해킹할 수 있는 컴퓨터의 개수를 증가시켜 주면 된다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>>link(10001);
int computer[10001];
bool visited[10001];
int hacked = 0;

// 컴퓨터의 관계를 탐색하며 해킹할 수 있는 컴퓨터의 수를 증가시켜 준다.
void dfs(int st)
{
	visited[st] = true;
	
	for (int next : link[st])
	{
		if (!visited[next])
		{
			dfs(next);
			hacked++;
		}
	}
}

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

	int N, M, MAX = 0;
	cin >> N >> M;

	// A를 B가 신뢰할 경우, B가 A를 공격해야 하니 순서를 바꿔서 저장해 준다.
	for (int i = 0; i < M; i++)
	{
		int u, v;
		cin >> u >> v;

		link[v].push_back(u);
	}

	//DFS탐색이 끝날 때 마다 해킹할 수 있는 컴퓨터의 최대값을 갱신해준다. 
	for (int i = 1; i <= N; i++)
	{
		fill(visited, visited + 10001, false);
		hacked = 0;

		dfs(i);
		computer[i] = hacked;

		if (MAX < hacked)
		{
			MAX = hacked;
		}
	}

	for (int i = 1; i <= N; i++)
	{
		if (computer[i] == MAX)
		{
			cout << i << " ";
		}
	}
}