백준 1325 효율적인 해킹

여타 다른 BFS 문제처럼 

각 노드별로 그 노드에서 도달할 수 있는 노드의 갯수를 계산해서

최대값을 가진 노드(들)을 출력하면 되는 문제이다.

그런데 이 문제는 4가지의 특징을 가지고 있다.

1. 메모리

평소에 하듯이 adj 배열을 2차원 배열로 선언해버리면

10000 * 10000 * 4byte = 381MB의 메모리를 먹고

short를 써도 190MB를 먹는다

따라서 가변 배열을 써야 한다.

링크는 10만개로 한정되어 있으니 가변 배열을 쓸 경우 100,000 * 4byte라서 1메가도 안된다.

2. 방향그래프

이 그래프는 다른 문제와 다르게 방향 그래프이다

"A가 B를 신뢰한다"

라는 문장은

B->A

와 동치이다.

이것을 유념해두고 문제를 풀어야 한다.

3. 입력

만약 cin으로 입력을 받으면

입력 받는 숫자가 꽤 있기 때문에 (20만개) 조금 느릴거다.

scanf로 받자.

4. 여러번의 BFS 탐색

1번노드에서 방문한 노드더라도, 

2번 노드에서 새로 탐색을 할때는 방문하지 않은 노드이다.

따라서 isVisit배열을 구별할 필요가 있는데,

만약 isVisit배열을 노드별로 따로 만들면 

역시나 10000 * 10000의 데이터가 필요하게 된다.

그렇게 하지말고 isVisit를 bool이 아닌 int의 1차원 배열로 선언하고,

isVisit에 true나 false를 저장하는 것이 아닌, 현재 탐색을 시행하고 있는 루트의 번호를 넣으면 된다.

그렇게 하면, 2번 노드에서 탐색을 시작할때는 1번노드에서 탐색한 노드(isVisit에 1이라고 저장되어 있게 된다)는 아직 방문하지 않은 것으로 파악하기 때문에

간단히 처리할 수 있게 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

vector<vector<int>> adj(10001, vector<int>());
int adjSize[10001];
int N, M;
vector<int> graphSize(10001, 0);
vector<int> isVisit(10001, -1);

int main() {
	scanf("%d %d", &N, &M);

	int start, end;
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &end, &start);
		end--;
		start--;
		adj[start].push_back(end);
		adjSize[start]++;
	}
	
	for (int i = 0; i < N; i++) {
		int rootNum = i;
		if (isVisit[i] != rootNum) { //지금 루트에서 시작하는 탐색으로는 방문하지 않음

			queue<int> bfs;
			bfs.push(i);
			isVisit[i] = rootNum;
			graphSize[rootNum]++;

			while (!bfs.empty()) {
				int now = bfs.front();
				bfs.pop();
				for (int iter = 0; iter < adjSize[now]; iter++) {
					int next = adj[now][iter];
					if (isVisit[next] != rootNum) { 
						bfs.push(next);
						isVisit[next] = rootNum;
						graphSize[rootNum]++;
					}
				}
			}


		}
	}

	int max = 0;
	for (int i = 0; i < N; i++) {
		if (graphSize[i] > max) max = graphSize[i];
	}
	bool first = true;
	for (int i = 0; i < N; i++) {
		if (graphSize[i] == max) {
			if (!first) {
				cout << " ";
			}
			first = false;
			cout << i + 1;
		}
	}

	return 0;
}

막히지 않고 코드를 쭉쭉 썼는데 한방에 맞춰서 조금 뿌듯

컨디션이 좋은듯