인프런 커뮤니티 질문&답변

안녕하세요 강사님, 강의를 듣다가 동전 문제를 BFS로 풀 수 있을거 같아 이렇게 풀었는데, 괜찮은 코드인지 여쭤보고 싶습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M, count;
    static int[] arr;
    static Queue<Integer> queue = new LinkedList<>();

    public void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            queue.offer(arr[i]);
        }
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
    }

    public int BFS() {
        while (!queue.isEmpty()) {
            count++;
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                int value = queue.poll();
                for (int X : arr) {
                    int data = value + X;
                    if (data == M) return count+1; // 동전의 값을 Queue에 삽입 전에 체크하기 때문에 +1를 추가해서 리턴
                    if (data < M) queue.offer(data);
                }
            }
        }
        return count;
    }

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.input();
        System.out.println(main.BFS());
    }
}