[백준] 1325. 효율적인 해킹

문제

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

풀이

질문들을 보면 런타임 에러, 시간 초과 등이 있는데, 틀린 이유야 여러가지겠지만 정리해보면

런타임 에러 - 배열 크기를 arr[10000][10000]으로 잡아서 주로 문제가 생기는 것 같은데, 메모리 계산을 한번 해보면 상당히 크다는 것을 알 수 있다. 인접 행렬 대신 인접 리스트로 만들도록 하자.

시간 초과 - 주로 사이클을 고려하지 않아서 생기는 것 같다. 특정 노드를 탐색 완료 했을 때는 방문 표시를 해주도록 하자.

참고로 문제 조건이 "A가 B를 신뢰한다."의 의미를 가지므로 B가 해킹당했을 때 A도 해킹당한다. 즉 B -> A 의 방향을 가지게 된다. 방향에 주의하자.

SCC 알고리즘이라는 특수한 알고리즘으로 해결 가능하다는데, 아직 공부해보지 않아서 공부한 후에 이 문제와 함께 포스팅을 하겠다. 하지만 이 문제는 완전 탐색만으로도 해결 가능하다. (사실 SCC 알고리즘이 DFS 기반이라는데, 그렇담 별 차이 없을 것 같다.)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;

int N, M;
vector<int> v[10011];
vector<pair<int, long long> > vv;
int visited[10011];

bool compare(pair<int, long long> &a, pair<int, long long> &b){
    if(a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}


void bfs(){

    long long cnt = 1;
    for(int i = 1; i <= N; i++){
        if(v[i].size() > 0){
            queue<int> q; q.push(i); cnt = 1;
            for(int i = 0; i <= N; i++){
                visited[i] = 0;
            }
            visited[i] = 1;
            while(!q.empty()){
                int com = q.front(); q.pop();
                for(int j = 0; j < v[com].size(); j++){
                    if(visited[v[com][j]] == 0){
                        visited[v[com][j]] = 1;
                        q.push(v[com][j]);
                        cnt++;
                    }
                }
            }
            vv.push_back(make_pair(i, cnt));
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int a, b; cin >> a >> b;
        v[b].push_back(a);
    }
    bfs();
    sort(vv.begin(), vv.end(), compare);
    for(int i = 0; i < vv.size(); i++){
        long long MAX = vv[0].second;
       if(vv[i].second != MAX) break;
        cout << vv[i].first << " ";
    }
    
    return 0;
}