[알고리즘] 백준 1325번: 효율적인 해킹 (C++), 성장을 체감한 문제

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

1325번: 효율적인 해킹

1달 전에 틀렸던 문제를 다시 푼 거라 오랜만에 성장했음을 체감했어서 기분이 좋은 문제였다.

메모리 초과로 틀렸던 문제였는데 이유는 2가지로 추려진다.

1. 배열의 크기가 너무 크다.
2. 방문 체크를 하지 않아서 그렇다.

>> 사실 이유는 2번이다. 하지만, 접근했던 방법이 1~2번이라 적어보았다.

여담이지만 다익스트라로 돌렸다가 시간 초과가 나왔어서 알게 된 방법이다.

 

[1. 배열의 크기가 너무 크다.]

배열의 크기가 너무 커서 기존의 BFS가 1~N까지 연결되어있나 확인하는 게 메모리 초과를 유발한다고 생각했다.

(그럴 수도 있겠지만 방문 체크를 하지 않아서다.)

while (!q.empty()) {
	int front = q.front();
	q.pop();
	for (int i = 1; i <= n; i++) { // 해당 부분
		if (map[front][i]) {
			q.push(i);
			cnt++;
		}
	}
}

그래서 map을 2차원 정적 배열이 아닌 2차원 동적 배열로 선언하여 고쳐주었다.

// 선언
vector<int> map[10001];
// BFS의 일부분
for (int i = 0; i < map[front].size(); i++) { // for의 범위가 줄어듬
	int next = map[front][i];
	if (!visited[next]) {
		visited[next] = 1;
		cnt++;
		q.push(next);
	}
}

 

[2. 방문 체크를 하지 않아서 그렇다.]

아무래도 이때 당시에 방문을 체크하지 않아도 TC를 통과한다는 생각에 방문 체크를 하지 않았던 거 같다. 방문 체크를 하지 않으면 서로서로 신뢰하는 컴퓨터들이 생기는 경우가 있어서 무조건 방문 체크를 해줘야 한다. 그렇지 않으면 무한 루프가 발생하게 된다.

vector<int> map[10001];
bool visited[10001] = { 0, };

int bfs(int value) {
	int cnt = 1;
	visited[value] = 1;
	queue<int> q;
	q.push(value);
	while (!q.empty()) {
		int front = q.front();
		q.pop();
		
		for (int i = 0; i < map[front].size(); i++) {
			int next = map[front][i];
			if (!visited[next]) {
				visited[next] = 1;
				cnt++;
				q.push(next);
			}
		}
	}

	return cnt;
}

 

이 부분을 제외하고도 최댓값을 구하는 과정에서 과거와는 다른 코드를 보고, 성장했음을 체감했어서 뿌듯했다.

(과거의 코드도 올려두겠다.)

[AC 코드]

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#define pii pair<int, int>
using namespace std;

int n, m;
vector<int> map[10001];
bool visited[10001] = { 0, };

int bfs(int value) {
	int cnt = 1;
	visited[value] = 1;
	queue<int> q;
	q.push(value);
	while (!q.empty()) {
		int front = q.front();
		q.pop();
		
		for (int i = 0; i < map[front].size(); i++) {
			int next = map[front][i];
			if (!visited[next]) {
				visited[next] = 1;
				cnt++;
				q.push(next);
			}
		}
	}

	return cnt;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;

	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		map[b].push_back(a);
	}

	vector<int> result;
	int maxValue = 0;
	for (int i = 1; i <= n; i++) {
		int bfsResult = bfs(i);
		memset(visited, 0, sizeof(visited));
		if (bfsResult > maxValue) {
			maxValue = bfsResult;
			result.clear();
			result.push_back(i);
		}
		else if (bfsResult == maxValue) {
			result.push_back(i);
		}
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << ' ';
	}

	return 0;
}

[과거의 코드 (메모리 초과)]

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int n, m;
int map[10001][10001] = { 0, };
bool visited[10001] = { 0, };

int bfs(int value) {
	int cnt = 1;
	queue<int> q;
	q.push(value);
	while (!q.empty()) {
		int front = q.front();
		q.pop();
		for (int i = 1; i <= n; i++) {
			if (map[front][i]) {
				q.push(i);
				cnt++;
			}
		}
	}

	return cnt;
}

int main() {
	cin >> n >> m;

	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		map[b][a] = 1;
	}

	vector<pair<int, int>> arr;
	int maxValue = 0;
	for (int i = 1; i <= n; i++) {
		int bfsResult = bfs(i);
		arr.push_back(make_pair(i, bfsResult));
		maxValue = max(maxValue, bfsResult);
	}

	for (int i = 0; i < n; i++) {
		if (arr[i].second == maxValue) {
			cout << arr[i].first << ' ';
		}
	}

	return 0;
}