Javaにおいて多次元配列のfor文より高速なdeepコピーの方法を教えてください

Question

現在,AtCoderでABC204-Cを解いています。
以下のようなコードを用いた結果、TLEとなりました。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner scanner = new Scanner(System.in);
    	
    	int N = scanner.nextInt();
    	boolean[][] can = new boolean[N][N];
    	boolean[][] befor = new boolean[N][N];
    	int M = scanner.nextInt();
    	int ans = 0;
    	
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++) {
    			befor[i][j] = true;
    		}
    	}
    	
    	for (int i = 0; i < N; i++) {
    		can[i][i] = true;
    	}
    	
    	for (int i = 0; i < M; i++) {
    		int from = scanner.nextInt();
    		int to = scanner.nextInt();
    		
    		can[from - 1][to - 1] = true;
    	}
    	
    	while (can != befor) {
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				befor[i][j] = can[i][j];
    			}
    		}
    		
    		for (int i = 0; i < N; i++) {
    		    for (int j = 0; j < N; j++) {
    			    if (can[i][j]) {
    				    for (int k = 0; k < N; k++) {
    					    can[i][k] |= can[j][k];
    				    }
    			    }
    		    }
    		}
    	}
    	
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++) {
    			if (can[i][j]) {
    				ans++;
    			}
    		}
    	}
    	
    	System.out.println(ans);
    }
}

元々はwhile内の

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        befor[i][j] = can[i][j];
    }
}

を

befor = can;

としていたため実行スピードに問題はなかったのですが、前述の通り変更した事により、実行時間が非常に伸びてしまいました。

多次元配列のdeepコピーの方法を検索してみましたが、for文を用いたものしか見当たらず、より高速な方法がないものかと思い質問いたします。

Answer 1

問題となっているのはコピーの速度ではないと思われます。
実際に「入力例1」で実行してみると、計算が終わらないことが分かります。

計算が終わらない理由は、以下のwhileループを抜けられないためです。

while (can != befor) {

ここでは中身まで含めて比較したかったのではないかと想われますが、実際には参照が同じであるかを判定していることになります。以下、参考までに、サンプルコードを挙げておきます。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Boolean[] a = new Boolean[10];
        Boolean[] b = new Boolean[10];
        Boolean[] c;
        c = a;
        System.out.println(a == b);
        System.out.println(a == c);
        System.out.println(Arrays.deepEquals(a, b));
        System.out.println(Arrays.deepEquals(a, c));
    }
}

Comments

[lotoka]

回答して頂き有難うございます。比較の際も注意が必要というのは盲点でした。