동전교환문제

송아지 찾기문제 처럼 풀어봤는데 BFS로 푼다고 풀었는데 맞나요? import java.util.ArrayList; import java.util.Scanner; import java.util.Queue; import java.util.LinkedList; public class Main { public int BFS(int target, int typesOfCoin, int[] coins, int[] check) { Queue q = new LinkedList(); check[target] = 1; q.offer(target); int level = 0; while (!q.isEmpty()){ int size = q.size(); for (int i = 0; i int exchange = q.poll(); for (int j = 0; j int nextExchange = exchange - coins[j]; if (nextExchange > 0 && check[nextExchange] == 0) { check[nextExchange] = 1; q.offer(nextExchange); } else if (nextExchange == 0) return (level + 1); } } level++; } return (-1); } public static void main(String[] args){ Main T = new Main(); Scanner in=new Scanner(System.in); int typesOfCoin = in.nextInt(); int[] coins = new int[typesOfCoin]; for (int i = 0; i int target = in.nextInt(); int[] check = new int[target + 1]; System.out.println(T.BFS(target, typesOfCoin, coins, check)); return ; } }