kangtak6291님의 게시글

질문&답변

동전교환문제

송아지 찾기문제 처럼 풀어봤는데 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 ; } }