[백준] 1325번 효율적인 해킹 - C++ (DFS, 그래프)

발상

1. 우선 그래프를 이용하는 문제인데 - A가 B를 신뢰할 경우 B를 해킹하면 A도 해킹할 수 있다는 것은, B가 부모 노드이고 A가 자식 노드인 것으로 생각하였다. B->A로 간선이 이어져서 B에서 해킹할 수 있는 자식 노드들을 모두 동시에 해킹할 수 있는 것들로 보았다.

2. DFS를 이용해 1~N까지 각 노드에서 출발했을 때 총 몇 개의 노드를 방문할 수 있는지를 계산하면 되는 문제이다.

3. dfs 함수를 int로 설정하였다. for문을 이용해 1~N까지 반복문을 설정하고, 각 node에서 출발하여 새로운 node를 방문할 때 (check값이 false인 자식 노드) ans에 해당 node에서의 dfs 값을 더하도록 했다. (해당 노드+거기에 연결된 자식 노드의 수) 

4. 반환된 ans값을 ans배열에 저장하고, 한 과정이 끝날 때마다 check배열을 초기화해 준다. 이것 때문에 시간 초과가 뜰까봐 걱정했는데 다행히 뜨지 않았다. 

5. ans값을 모두 구하고 나면, ans 배열에서 최댓값을 찾는다. 이 때의 i값을 answer에 저장해둔다.

6. total vector에 ans배열에서 최댓값과 같은 i값을 모두 push해 준다.

7. 이것을 오름차순 정렬하고 출력한다. 

 

소스코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool check[10001]; // 전역변수는 선언시 자동초기화  
vector<int> input[10001]; 
int ans[10001] = {0,};

int dfs(int node){
	int ans = 1;
	check[node] = true;
	for(int j=0; j<input[node].size(); j++){
		int temp = input[node][j];
		if(check[temp] == false){
			ans += dfs(temp);
		}
	}
	return ans;
}
int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	
	for(int i=0; i<M; i++){
		int t1, t2;
		cin >> t1 >> t2;
		input[t2].push_back(t1);
	}
	
	for(int i=1; i<=N; i++){
		ans[i] = dfs(i);
		for(int j=1; j<=N; j++){
			if(check[j] == true) check[j] = false;
		}
	}
	int maxx = 0;
	int answer;
	vector <int> total;
	for(int i=1; i<=N; i++){
		if(ans[i] > maxx){
			answer = i;
			maxx = ans[i];
		}
	}
	total.push_back(answer);
	for(int i=1; i<=N; i++){
		if(ans[i] == maxx && i!=answer){
			total.push_back(i);
		}
	}
	sort(total.begin(), total.end());
	for(int i=0; i<total.size(); i++){
		cout << total[i] << " ";
	}
	return 0;
}

 

우선 dfs 함수 부분만 살펴보면 다음과 같다. 이전 문제 (11724번: 연결 요소의 개수) 에서는 void 함수를 사용하였으나, 이번 문제에서는 해당 node에서 방문 가능한 자식 node의 개수 값(int) 를 반환해야 하므로 int함수로 정의하였다. 

int dfs(int node){
	int ans = 1; // 일단 방문한 노드(나) 의 값 1을 설정해 준다. 
	check[node] = true;
	for(int j=0; j<input[node].size(); j++){
		int temp = input[node][j];
		if(check[temp] == false){
			ans += dfs(temp); //이 노드에서 방문가능한 그 아래 노드의 수 (dfs(temp)) 를 ans값에 더한다.
		}
	}
	return ans; // ans값을 반환한다. 
}

최종적으로 이 함수는 입력된 값에서 탐색을 시작했을 때 방문 가능한 node의 수를 반환하게 된다. 

 

	for(int i=0; i<M; i++){
		int t1, t2;
		cin >> t1 >> t2;
		input[t2].push_back(t1);
	}

그래프의 간선을 입력하는 부분이다. A가 B를 신뢰할 경우 B->A로 이어지는 것이므로 input[t2]에 t1값을 push해준다. 

 

	for(int i=1; i<=N; i++){
		ans[i] = dfs(i);
		for(int j=1; j<=N; j++){
			if(check[j] == true) check[j] = false;
		}
	}

1부터 N까지의 node에서 각각 방문 가능한 node의 개수를 앞서 설명한 dfs를 이용해 얻고, ans배열에 저장하였다.

매번 check 배열을 초기화해 주어야 한다. 

 

	int maxx = 0;
	int answer;
	vector <int> total;
	for(int i=1; i<=N; i++){
		if(ans[i] > maxx){
			answer = i;
			maxx = ans[i];
		}
	}
	total.push_back(answer);
	for(int i=1; i<=N; i++){
		if(ans[i] == maxx && i!=answer){
			total.push_back(i);
		}
	}
	sort(total.begin(), total.end());
	for(int i=0; i<total.size(); i++){
		cout << total[i] << " ";
	}
	return 0;

ans배열에서 최댓값을 찾고, 그 값과 같은 값을 가지는 항의 index를 모두 total 배열에 넣어주었다.

오름차순 정렬을 하고 출력해 주면 끝.~~!!!!