백준 1325 효율적인 해킹 c++ (dfs)

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

1325번: 효율적인 해킹

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

알고리즘 분류

 

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

핵심 풀이는 다음과 같다.

1. dfs로 간선으로 연결된 노드들을 탐색해 연결된 노드들을 카운트한다.

2. 각 노드의 카운터 순으로 내림차순 정렬하고, 노드들의 카운터가 같다면 노드의 번호 순으로 오름차순 정렬한다.

 

우선 인접 리스트 그래프 vector<int> graph[]를 준비하고, 3이 1을 신뢰하는 경우

1을 해킹하면 3도 해킹할 수 있기 때문에, 그래프의 방향은 1->3이다.

따라서 graph[1].push_back(3)을 해준다. 단방향 그래프이기 때문에 반대로 연결은 하지 않는다.

※인접 행렬 그래프보다 인접 리스트 그래프가 메모리 부분에서 효율적이기 때문에 웬만하면 인접 리스트 그래프를 사용
  하는 습관을 들이자. 해당 문제에서도 인접 행렬 그래프를 사용하면 메모리 초과가 뜬다고 한다.

 

그래프를 연결해 주고, 모든 노드를 탐색하여 카운트와 노드 번호를 배열에 저장한다.

vector<pair<int,int>>에 저장하고 algorithm헤더의 sort를 커스텀하는 방법도 있지만,

본인은 우선순위큐에 저장하고, 우선순위큐의 sort 방식을 커스텀했다.

 

이후 가장 높은 카운트(큐의 맨 앞)와 같은 노드 번호들을 오름차순(큐의 순서대로)으로 출력하면 된다. 

결과는 3162ms로 통과하였는데 아마 그래프에 사이클이 있는 경우, 사이클에 있는 노드를 하나만 탐색하고,

사이클에 있는 나머지 노드들에 카운트를 동일하게 저장해 주면 더 빠른 결과가 나올 것이다.

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
vector<int> graph[10001];
bool visited[10001];
int n,m,cnt;
struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		if (a.first == b.first)
			return a.second > b.second;
		return a.first < b.first;
	}
};


void dfs(int start) {

	cnt++;
	visited[start] = true;
	for (int i = 0; i < graph[start].size(); i++) {

		if (!visited[graph[start][i]]) {
			
			dfs(graph[start][i]);
		}

	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

	for (int i = 0; i < m; i++) {
		int to, from;
		cin >> to >> from;
		graph[from].push_back(to);
	}
	for (int i = 1; i <= n; i++) {
		dfs(i);
		pq.push({ cnt,i });
		//cout << i << ' ' << cnt << '\n';
		cnt = 0;
		memset(visited, false, sizeof(visited));
	}
	if (!pq.empty()) {
		int first = pq.top().first;
		int result = pq.top().second;
		cout << result << ' ';
		pq.pop();
		while (!pq.empty()&& first==pq.top().first) {
			cout << pq.top().second << ' ';
			pq.pop();
		}
	}

	return 0;
}