백준 1325 효율적인 해킹 (C++)

1325번: 효율적인 해킹

dfs나 bfs를 이용한 문제이다. 주어지는 신뢰하는 관계를 먼저 vector에 차례대로 저장해주었다. 그리고 각 인덱스에서 탐색을 하면서 카운트를 해주어 저장해주었고 최댓값을 가지는 인덱스를 출력해주었다. 이 문제는 dfs와 bfs 두가지 방식으로 문제를 풀어보았다. dfs의 경우 사이클이 돌 수 있어 시간 초과가 나올 수 있기때문에 방문 체크를 잘 해주어야했다. 어렵지 않게 풀 수 있었다.

DFS

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, M;
vector<int> v[10001];
bool visit[10001];
int cnt = 0;
int mm = 0;
int result[10001];

void dfs(int n) {
    cnt++;

    for (int i = 0; i < v[n].size(); i++) {
        int nn = v[n][i];

        if (visit[nn]) continue;

        visit[nn] = true;
        dfs(nn);
    }
}

void solution() {
    for (int i = 1; i <= N; i++) {
        memset(visit, false, sizeof(visit));

        cnt = 0;

        visit[i] = true;
        dfs(i);

        result[i] = cnt;
        mm = max(mm, cnt);
    }

    for (int i = 1; i <= N; i++) {
        if (result[i] == mm) {
            cout << i << " ";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

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

    solution();

    return 0;
}

BFS

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

using namespace std;

int N, M;
vector<int> v[10001];
bool visit[10001];
int result[10001];
int mm = 0;

void bfs(int n) {
    queue<int> q;
    int count = 1;

    q.push(n);
    visit[n] = true;

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

        q.pop();

        for (int i = 0; i < v[a].size(); i++) {
            int na = v[a][i];

            if (visit[na]) continue;

            q.push(na);
            visit[na] = true;
            count++;
        }
    }

    result[n] = count;
    mm = max(count, mm);
}

void solution() {
    for (int i = 1; i <= N; i++) {
        memset(visit, false, sizeof(visit));

        bfs(i);
    }

    for (int i = 1; i <= N; i++) {
        if (result[i] == mm) {
            cout << i << " ";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

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

    solution();

    return 0;
}