[백준 C++] 1325 효율적인 해킹

문제

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

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

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

입력

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

출력

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

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

풀이

문제에서 보면 컴퓨터간 연결이 단방향임을 체크해야한다.
따라서 단방향의 연결을 나타내는 vector< int> edge[n] (n은 컴퓨터번호)에 추가했다.
큐자료구조를 썼으니 dfs에 가깝게 문제를 풀었는데, 타 언어로하면 최적화를 해줘야된다고는 한다.. c로는 시간초과, 메모리초과없이 풀린다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::pair; using std::queue;
int n, m;
vector<int> edge[10001]; //간선정보
vector<pair<int, int>> res; //컴퓨터번호 : 해킹가능한컴퓨터수
bool* visited;

void printAll() {
	int max = 0;
	for (int i = 0; i < res.size(); i++) {
		if (max <= res[i].second)
			max = res[i].second;
	}

	for (int i = 0; i < res.size(); i++)
		if (res[i].second == max)
			printf("%d ", res[i].first);

}

void func() {
	visited = new bool[n + 1];
	queue<int> q;
	for (int k = 1; k <= n; k++) {
		memset(visited, 0, (n+1)*sizeof(bool)); //방문배열 초기화
		while (!q.empty()) q.pop(); //큐 초기화
		int r = 0; //해킹가능한 컴퓨터수...카운트
		q.push(k);
		visited[k] = true;
		while (!q.empty()) {
			int num = q.front();
			q.pop();
			
			for (int i = 0; i < edge[num].size(); i++) { //k번컴퓨터에연결된 컴퓨터만큼 반복
				int next = edge[num][i];
				if (!visited[next]) {
					visited[next] = true;
					r++;
					q.push(next);
				}
			}
		}

		if (r != 0) 
			res.push_back({ k, r });
		
	}
}

int main(int a, int b) {
	scanf("%d%d", &n, &m);
	while (m--) {
		scanf("%d%d", &a, &b);
		edge[b].push_back(a);
	}

	func();

	printAll();

	return 0;
}