[BOJ/C++] 1325 효율적인 해킹

문제 링크 https://www.acmicpc.net/problem/1325

📝 문제

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

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

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

💻 코드

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

int N, M;
vector<int> arr[10001];
int visited[100001];
int cnt;
int maxCnt = 0;
vector<int> result;

void dfs(int now)
{
	visited[now] = 1;
	cnt++;

	for (int i = 0; i < arr[now].size(); i++) {
		int next = arr[now][i];

		if (visited[next] == 1) continue;

		dfs(next);
	}
}

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

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int from, to;
		cin >> to >> from;
		arr[from].push_back(to);
	}

	for (int i = 1; i <= N; i++) {
		cnt = 0;
		fill_n(visited, 100001, 0);
		dfs(i);

		if (cnt > maxCnt) {
			maxCnt = cnt;
			result.clear();
			result.push_back(i);
		}
		else if (cnt == maxCnt) {
			result.push_back(i);
		}
	}

	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << " ";
	}
}

📌 해결방법

1. A가 B를 신뢰하면, B를 해킹하면 A도 해킹할 수 있기 때문에 from, to 를 반대로 받아주기!
2. 1번부터 dfs를 진행하면서 몇개의 컴퓨터는 해킹할 수 있는지 cnt에 기록
3. cnt > maxCnt라면 maxCnt를 갱신해주고 vector 배열을 초기화 한 후에 result.push_back(i)를 통해 값 넣기
4. cnt == maxCnt 라면 이미 있는 값 뒤에 현개 값 넣기!

💡 배운 점

- fill_n() 함수

• std::fill_n(배열 이름, 초기화할 요소의 개수, 초기화할 값) 형태로 사용
• 배열을 특정값으로 초기화 할 때 사용

fill_n(visited, 100001, 0);

• 이렇게 작성하면 visited 배열을 0으로 초기화

---

✔ 느낀 점

메모리초과와 시간초과로 틀렸던 문제.....,
아니 처음에는 양방향이라서 visited 없이도 될 줄 알고 인접행렬방식으로 작성했는데 메모리초과.....
그래서 인접리스트방식으로 벡터를 사용하는 코드로 바꿨다 근데 이번에는 시간초과..!!!!!!
그래서 visited배열도 사용해서 코드를 고쳤는데
원래 벡터 초기화하는 부분을 저렇게 작성했었는데 초기화가 안되는지 디버깅중에 답이 계속 이상하게 나왔다.

	for (int i = 1; i <= N; i++) {
		cnt = 0;
		visited[100001] = {0, };
		dfs(i);
	}

그래서 찾아보니 이런 방법으로는 초기화가 안되는 것 같다. 그래서 fill_n 함수 사용하니까 바로 통과했다..ㅎ 험난한 여정