[c++][그래프] 백준 1325번: 효율적인 해킹

 

 

 

 

 

 

문제풀이

1. 'A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다'에서 그래프의 방향을 B -> A 단방향으로 보고 노드를 저장한다.

2. 시작 노드에서 끝 노드까지의 개수를 구해야 하므로 DFS 방식을 이용한다.

3. 노드를 방문할 때 노드의 개수(=check)를 센다.

4. 노드의 개수를 구했을 때 지금까지 구했던 노드의 개수보다 클 경우 이전에 구했던 값들을 지우고 현재 값을 넣는다. 노드의 개수가 이전에 구했던 노드의 개수와 같다면 현재 값도 함께 넣는다.

 

 

 

코드

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

using namespace std;

vector<vector<int>> graph;
vector<int> g;
bool visited[10001] = { false };
int check;

void DFS(int v) {
	visited[v] = true;

	for (int i = 0; i < graph[v].size(); i++) {
		int next = graph[v][i];
		if (!visited[next]) {
			check++; // 노드의 개수
			DFS(next);
		}
	}
}

int main() {
	int n, m;
	vector<int> count;

	cin >> n >> m;

	graph.resize(m + 1);
	graph.push_back(g);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[b].push_back(a); // 단방향
	}

	int max = 0;
	for (int i = 1; i <= n; i++) {
		memset(visited, false, sizeof(visited)); // 노드를 확인하기 전에 이전 노드에서 방문했던 노드들을 리셋한다.
		check = 0;
		DFS(i);

		if (max == check) {
			count.push_back(i);
		}
		else if(max < check) {
			max = check;
			count.clear();
			count.push_back(i);
		}
	}

	sort(count.begin(), count.end());
	for (int i = 0; i < count.size(); i++) {
		cout << count[i] << " ";
	}

	return 0;
}

 

 

참고 블로그

 

https://rile1036.tistory.com/140

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