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

📝 문제

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

💻 코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int n, m;
vector<int> arr[10001];
bool visited[10001];
int MAX = 0;

int bfs(int first) {
	queue<int> q;
	q.push(first);
	visited[first] = true;
	int cnt = 0;

	while (!q.empty()) {
		int start = q.front();
		q.pop();

		for (auto& end : arr[start]) {
			if (visited[end]) continue;
			visited[end] = true;
			q.push(end);
			cnt += 1;
		}
	}

	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int end, start;
		cin >> end >> start;
		arr[start].push_back(end);
	}	// 그래프 생성(인접행렬)

	vector<int> vmax;

	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		int hack = bfs(i);
		if (hack > MAX) {
			MAX = hack;
			vmax.clear();
			vmax.push_back(i);
		}
		else if (hack == MAX) {
			vmax.push_back(i);
		}
	}

	sort(vmax.begin(), vmax.end());

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


	return 0;
}

📌 해결방법

1. 단방향 그래프를 인접 리스트(vector)로 구현
2. bfs를 통해 해킹할 수 있는 컴퓨터 카운트

💡 배운 점

memset

메모리의 내용을 원하는 크기만큼 특정 값으로 초기화 하는 함수로 C/C++에서 사용 가능

#include <cstring>
void* memeset(void* str, int value, size_t size);
memset(배열, 원하는 값, 배열 크기)

장점: for로 초기화 하는 것보다 빠르다.
단점: memset 함수는 1바이트 단위로 초기화하므로 int형은 0을 제외한 수는 사용 불가능하다.
*fill 함수로 대체 가능하다.

---

✔ 느낀 점

이 문제 역시 new rice님을 보고 따라 풀었는데 메모리 초과가 계속 나서 멘붕이었다;;
먼저 인접행렬을 인접리스트로 바꿨다. => 근데 또 메모리 초과남
그래서 visited를 fill_n으로 초기화 => 이상한 에러나고 값 안나옴...

마지막으로 visited를 memset으로 초기화했더니 성공했다.😂
요즘 알고리즘을 열심히 안풀었는데 정말 폼 다 떨어졌다고 느껴지는 문제였다... 곧 코테봐야 되는데
많이 쫄린다... ㅎㅎㅎㅎ