흥미로운 알고리즘 - 루프 전략(Loop Strategy)

import java.util.*;

public class Main {
    static final int PRISONER = 100; // 죄수의 인원
    static final int LIMIT = PRISONER / 2; // 상자를 열어 볼 수 있는 제한
    static final int TRIALS = 100000; // 시행 횟수
    static ArrayList<Integer> box = new ArrayList<>();

    public static void main(String[] args) {
        // 각 전략을 실행함
        doStrategy(false); // false - 랜덤 전략
        doStrategy(true); // true - 루프 전략
    }

    // 전략 실행 및 성공 비율 계산 함수
    static void doStrategy(boolean flag) {
        int success = 0; // 모든 죄수가 찾은 경우 저장
        boolean isFind; // 한 명의 죄수가 번호를 찾았는지 저장

        // 시행 횟수만큼 반복
        newtrial : for(int t = 0; t < TRIALS; t++) {
            initBox();

            // i번째 죄수가 상자를 열어 봄
            for (int i = 0; i < PRISONER; i++) {
                // flag : true - 루프전략 / false - 랜덤전략
                if(flag) isFind = loopStrategy(i);
                else isFind = randomStrategy(i);

                // 자기 번호 못찾았을 경우
                if (!isFind) continue newtrial;
            }

            // 모든 죄수가 찾았으므로 성공 횟수 증가
            success++;
        }

        if(flag) System.out.println(String.format("루프 전략 (성공 / 시행 횟수) : %d / %d", success, TRIALS));
        else System.out.println(String.format("랜덤 전략 (성공 / 시행 횟수) : %d / %d", success, TRIALS));
    }

    // 랜덤 전략 함수
    static boolean randomStrategy(int number) {
        // 이미 방문한 상자 표시용
        HashSet<Integer> visit = new HashSet<>();

        // 제한 횟수만큼 상자를 열어봄
        for(int i = 0; i < LIMIT; i++) {
            int boxNum = -1; // 열어볼 상자 번호

            // 이미 열어 본 상자라면 다른 상자 선택
            do {
                boxNum = (int)(Math.random() * PRISONER);
            } while(visit.contains(boxNum));
            visit.add(boxNum); // 열어본 상자 목록에 추가

            // 자기 번호 찾았을 경우 true
            if(number == box.get(boxNum)) return true;
        }

        // 제한 횟수만큼 열어봤는데 못찾은 경우 false
        return false;
    }

    // 루프 전략 함수
    static boolean loopStrategy(int number) {
        // 다음에 열어 볼 상자
        int next = number;

        // 제한 횟수만큼 상자 열어봄
        for(int i = 0; i < LIMIT; i++) {
            if(number == box.get(next)) return true; // 자기 번호 찾은 경우 true
            next = box.get(next); // 상자에 있던 번호가 다음에 열어볼 상자가 됨
        }

        // 제한 횟수만큼 열어봤는데 못찾은 경우 false
        return false;
    }

    // 상자 초기화 함수
    static void initBox() {
        box.clear(); // 상자 비우기
        for(int i = 0; i < PRISONER; i++) box.add(i); // 상자에 번호 넣기
        Collections.shuffle(box); // 상자 무작위로 섞기
    }
}