런타임에러(ArrayIndexOutOfBound) 가 나는 이유

안녕하세요 강사님

강사님 강의 문제에 대한 질문이 아니라 답변하기 힘드시면 괜찮습니다.
강사님 강의를 다 듣고 추천해주신 백준 문제들을 풀다가 질문이 있어 질문드립니다.

백준 9019 문제에 관한 질문인데 백준에서 채점 받을때 ArrayIndexOutOfBound 가 나는 이유를 제 코드를 살펴봐도 어디서 문제이지 찾을 수 없어 질문드립니다.

9019 의 문제의 솔루션을 구글링 해봐도 다 똑같은 코드로만 작성을 해놔서 제가 작성한 코드가 어디가 문제였는지 알고 싶어 질문드립니다.

package Baekjoon;
import java.util.*;

class DSLR {
    public int result;
    public String command;
    DSLR(int result, String command) {
        this.result = result;
        this.command = command;
    }

}
public class _9019 {
    static boolean[] ch = new boolean[10000];
    static ArrayList<String> list = new ArrayList<>();
    public void BFS(int input, int output) {
        Arrays.fill(ch, false);
        Queue<DSLR> q = new LinkedList<>();

        q.offer(new DSLR(input, ""));

        while(!q.isEmpty()) {

            DSLR tmp = q.poll();
            if (tmp.result == output) {
                list.add(tmp.command);
                break;
            }
            for (int i = 0; i < 4; i++) {
                if(i == 0) {
                    int next_result = (tmp.result * 2) % 10000;
                    if (!ch[next_result]) {
                        String next_command = tmp.command + 'D';
                        ch[next_result] = true;
                        q.offer(new DSLR(next_result, next_command));
                    }
                }
                if (i == 1) {
                    int next_result = tmp.result - 1;
                    if (next_result == 0) next_result = 9999;
                    if (!ch[next_result]) {
                        String next_command = tmp.command + 'S';
                        ch[next_result] = true;
                        q.offer(new DSLR(next_result, next_command));
                    }
                }
                if (i == 2) {
                    int next_result = (tmp.result % 1000) * 10 + (tmp.result / 1000);
                    if (!ch[next_result]) {
                        String next_command = tmp.command + 'L';
                        ch[next_result] = true;
                        q.offer(new DSLR(next_result, next_command));
                    }
                }
                if (i == 3) {
                    int next_result = (tmp.result % 10) * 1000 + tmp.result / 10;
                    if (!ch[next_result]) {
                        String next_command = tmp.command + 'R';
                        ch[next_result] = true;
                        q.offer(new DSLR(next_result, next_command));
                    }
                }
            }

        }

    }
 
    public static void main(String[] args) {
        _9019 T = new _9019();
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        for (int i = 0; i < test; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            ch[a] = true;
            T.BFS(a, b);
        }
        for(String x : list) {
            System.out.println(x);
        }
    }
}