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

문제 설명

https://www.acmicpc.net/problem/1325
컴퓨터 A가 컴퓨터 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리
첫 번째 줄에 입력 N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다.
둘째 줄부터 M개의 줄에 A B와 같은 형식으로 입력이 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.
한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력하는 문제다.

아이디어

BFS

어떤 노드부터 시작해야 가장 깊게 탐색할 수 있는 지 찾으면 된다.
처음엔 bfs로 풀었다.
전체 컴퓨터의 수는 최대 9999개 이므로 2차원 배열int map[10000][10000]로 풀어서 제출했는데 메모리초과가 났다.
그래서 벡터 배열 vector<int> map[10001] 로 풀었더니 정답처리 됐다.😲

++ visited 처리 안해주면 queue에 추가하는 과정에서 메모리 초과나는 듯하다.

DFS

추가로 dfs로도 풀어봤다.
각 노드의 값을 1로 두고 dfs할 때마다 1씩 더해지는 식으로 풀었다.

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <memory.h>
using namespace std;
int n, m;
int mx;
int res[10001];
int visited[10001];
queue<int> q;
vector<int> map[10001];

int bfs(int x)
{
    q.push(x);
    visited[x] = 1;
    int cnt = 0;
    while (!q.empty())
    {
        int node = q.front();
        q.pop();

        for (int k : map[node])
        {
            if (visited[k])
                continue;
            visited[k] = 1;
            cnt++;
            q.push(k);
        }
    }
    return cnt;
}

int dfs(int x)
{
    visited[x] = 1;
    int cnt = 1;
    for (int i : map[x])
    {
        if (visited[i])
            continue;
        cnt += dfs(i);
    }
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    for (int i = 1; i <= n; i++)
    {
        memset(visited, 0, sizeof(visited));
        res[i] = bfs(i);
        mx = max(res[i], mx);
    }

    for (int i = 1; i <= n; i++)
    {
        if (res[i] == mx)
            cout << i << " ";
    }
}