[BOJ] 1325 효율적인 해킹 c++

문제 링크

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

핵심 알고리즘

그래프의 가장 기본적인 문제로 vector adj와 visited배열, 해킹하는 번호를 저장하는 cnt배열에 값을 저장하여 푸는 문제이다.

1부터 n까지 visited배열과 해킹하는 컴퓨터의 수를 저장하는 count값을 초기화한 후, 해킹한 다음, 가장 많은 컴퓨터의 수를 저장하는 big을 거쳐, cnt배열에 저장한다.

1부터 n까지 cnt배열을 돌기 때문에 자연스럽게 오름차순으로 출력된다.

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <unordered_map>
#include <map>
#include <cmath>
#include <sstream>
using namespace std;

vector<int> adj[10001];
int cnt[10001];
int big = 0;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    
    while (m--) {
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        int visited[10001];
        for (int j = 1; j <= n; j++)
            visited[j] = 0;

        int count = 0;

        queue<int> q;
        q.push(i);
        visited[i] = 1;

        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            count++;

            for (auto nxt : adj[cur]) {
                if (visited[nxt] == 0) {
                    q.push(nxt);
                    visited[nxt] = 1;
                }
            }
        }

        big = max(big, count);
        cnt[i] = count;
    }

    for (int i = 1; i <= n; i++)
        if (cnt[i] == big)
            cout << i << " ";
  
}