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

안녕하세요^^

레벨탐색으로 뻗다가 target 금액을 만나면 멈추는게 DFS보다 더 좋은 방법입니다. 잘하신 코드입니다.

송아지 찾기문제 처럼 풀어봤는데 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<Integer> q = new LinkedList<>(); check[target] = 1; q.offer(target); int level = 0; while (!q.isEmpty()){ int size = q.size(); for (int i = 0; i < size; i++) { int exchange = q.poll(); for (int j = 0; j < typesOfCoin; 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 < typesOfCoin; i++) coins[i] = in.nextInt(); int target = in.nextInt(); int[] check = new int[target + 1]; System.out.println(T.BFS(target, typesOfCoin, coins, check)); return ; } }

안녕하세요^^

BFS로 해결할 수 있는 방법이 있나요? 

저는 잘 모르겠어서....사실 이 문제는 다이나믹 문제인데 제가 DFS문제로 활용해본 것입니다.

BFS로 어떻게 한다는 건지 궁금하네요.