BOJ 1325 효율적인 해킹

문제출처 : https://www.acmicpc.net/problem/1325

1. 문제요약

- N개의 컴퓨터, 1 <= N <= 10,000

- M개의 신뢰관계, 1 <= M <= 100,000

- A가 B를 신뢰한다. => B를 해킹하면 A도 해킹할 수 있다. / A를 해킹하면 B는 해킹할 수 없다.

- M개의 A B 쌍이 주어지며, A가 B를 신뢰한다.

- 한 번에 가장 많은 컴퓨터를 해킹 할 수 있는 컴퓨터의 번호를 오름차순 출력

2. 접근방법

- 단뱡향 그래프

- 신뢰관계에 대해 int 더블배열을 쓰면 4 * 10,000 * 10,000 = 400,000,000byte = 400Mbyte로 메모리 초과

  => 더블 벡터로 입력 받음

- 하나의 컴퓨터에서 해킹 할 수 있는 모든 컴퓨터를 찾는다.

- 한 정점에서 시작하여 다시 그 정점을 방문하면 안되므로 체크 배열을 쓴다.

3. 시간복잡도

- 모든 정점의 갯수 N * 최대 쌍의 갯수 M = O(NM)

- NM = 10억 인데 5초 안에 들어오려나...3.8초 나옴

- SCC 라는 알고리즘을 쓰면 더 빨리 돌릴 수 있다는데 나중에 공부해야지

4. 회고

- 중간에 dp 처럼 아에 한번 방문한 정점은 다시는 방문하지 않아도 되지 않을까 해서 그렇게 했는데

  이렇게 하면 체크가 없어서 그래프가 싸이클을 만들면 무한루프로 빠져들어감......

  => 그래프에서는 싸이클을 생각해보자

- 한 정점(1 번)에서 시작해서 방문했던 정점을 재 방문 하는 경우(1 -> 2 -> 1)만 막아야지

  새로운 다른 정점(2 번)에서 시작해서 이전 정점에서 방문했던 정점(1 번에서 방문했던 정점들) 방문을 막으면 안됨

  쌍방 연결이나, 한 노드를 여러 노드가 방문할 수 있기 때문

  => 체크 배열 초기화 !!!!!!!

- 컴퓨터의 번호는 1 부터 시작하므로 배열의 크기는 n + 1 !!!!!!!!!

  for문 인덱스도 1 !!!!!!!

소스코드

#include<iostream>
#include<vector>
using namespace std;

int n, m;
int nodeNum[10001];
bool check[10001];
vector<vector<int> > tree;

int max(int a, int b){
	return ((a > b) ? a : b);
}

int dfs(int node){
	check[node] = true;

	int ret = 0;
	for (int i = 0; i < (int)tree[node].size(); i++)
		if (!check[tree[node][i]])
			ret += dfs(tree[node][i]) + 1;

	return ret;
}

int main(void){
	cin >> n >> m;
	tree.resize(n + 1);
	int a, b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		tree[b].push_back(a);
	}

	int maxV = 0;
	for (int i = 1; i <= n; i++){
		nodeNum[i] = dfs(i);
		maxV = max(maxV, nodeNum[i]);
		for (int j = 0; j <= n; j++)
			check[j] = false;
	}

	for (int i = 1; i <= n; i++)
		if (nodeNum[i] == maxV) cout << i << " ";
	cout << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]