1325 효율적인 해킹

BOJ::1325 효율적인 해킹

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

각각의 노드에 수렴하는 경로가 몇개인지 찾으면 된다.

처음에 2차원배열로 풀려 하니 시간초과가 나와서 인접행렬로 다시 풀어보니 통과했다.

그치만 통과했음에도 시간이 굉장히 오래걸림을 확인할 수 있었다.

더 좋은 방법이 있을까?

거의 같은 로직으로 코딩한 자바와 씨플플의 속도차이

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
class Main{
    
    static int n,m;
    static ArrayList<Integer> map[];
    static boolean check[];
    static int res[] = new int[10001];
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        map = new ArrayList[n+1];
        for(int i = 1 ; i <= n ; i++){
            map[i] = new ArrayList();
        }
        
        for(int i = 0 ; i < m ; i++){
            st=new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x].add(y);
        }
        
        for(int i =1; i<= n ;i++){
            check = new boolean[n+1];
            dfs(i);
        }
        
        int max = 0;
        for(int i =1 ; i <= n ; i++){
            if(max <res[i]){
                max = res[i];
            }
        }
        for(int i = 1 ; i <= n ; i++){
            if(res[i]==max){
                System.out.print(i+" ");
            }
        }
    }
    
    public static void dfs(int v){
        check[v]=true;
        for(int vv : map[v]){
            if(!check[vv]){
                dfs(vv);
                res[vv]++;
            }
        }
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;
 
int n,m;
vector<int> map[10001];
bool check[10001];
int res[10001];
 
void initCheckArray() {
    for (int i = 1; i <= n; i++) {
        check[i] = false;
    }
}
 
void dfs(int v) {
    check[v] = true;
    for (auto& vv : map[v]) {
        if (!check[vv]) {
            dfs(vv);
            res[vv]++;
        }
    }
}
 
int main() {
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        map[x].push_back(y);
    }
 
    for (int i = 1; i <= n; i++) {
        initCheckArray();
        dfs(i);
    }
 
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (max < res[i]) {
            max = res[i];
        }
    }
 
    for (int i = 1; i <= n; i++) {
        if (res[i] == max) {
            cout << i << " ";
        }
    }
 
}