Coin Change

문제 파악

coins 배열 안에 있는 값들로 amount를 만들어야 하는데 가장 적은 개수를 사용해 만드는 문제

만약 만들지 못하면 -1 반환

가장 적은 개수를 사용해야 하기 때문에 0부터 시작해서 차례대로 방문하면서 가장 처음 목표 금액에 도달했을 때가 가장 적은 개수를 이용하는 것
‘최소’의 동전으로 목표 금액을 만들어라 → BFS

BFS는 그래프나 트리에서 가장 가까운 노드부터 차례대로 탐색하는 알고리즘
시작 노드에서 가까운 노드부터 차례대로 탐색하며, 큐를 사용해 구현
BFS는 최단 경로 탐색에 유리한데, 모든 간선의 가중치가 동일할 때 먼저 방문한 경로가 항상 가장 짧기 때문
따라서 가장 먼저 도착한 경로가 곧 최단 경로

풀이

1. amount가 0일 때 0 반환
2. 큐와 방문 리스트를 선언하고 큐에 amount를 넣고 방문 처리를 해준다.
3. 현재 방문 노드를 큐에서 빼준 후 amount에서 각 코인 값을 뺀 값을 다음 노드로 설정하고 큐에 넣고 방문 처리를 해준다. → 현재 방문 노드가 0일 때까지 반복
   1. 처음에는 그냥 금액만 큐에 넣었는데 동전을 몇 개 썼는지까지 같이 저장해야 문제의 답을 도출할 수 있어서 넣기로 했다. → 큐에 배열을 넣기?
   2. queue = [[11, 0]] 이런 식으로 들어가게 됨 (남은 금액 11원, 사용한 동전 개수 0개)
   3. BFS가 시작되면 현재 노드를 큐에서 제거하고 다음 노드들을 넣은 다음 방문 처리

코드

class Solution {
    public int coinChange(int[] coins, int amount) {
        //amount가 0일 때 0 반환
        if (amount == 0) {
            return 0;
        }

        //큐와 방문 노드 선언
        Queue<int[]> queue = new LinkedList<>();
        boolean[] visited = new boolean[amount + 1];

        //큐에 넣고 방문 처리
        queue.add(new int[] {amount, 0});
        visited[amount] = true;

        //BFS 수행
        //큐가 빌 때까지
        while (!queue.isEmpty()) {
            //큐에서 현재 노드 꺼내기
            int[] currentNode = queue.poll();
            //현재 금액
            int currentAmount = currentNode[0];
            //사용한 동전 개수
            int coinCount = currentNode[1];

            //다음 노드들에 대해 설정
            for (int coin : coins) {
                int next = currentAmount - coin;

                //만약 다음 노드가 0이라면 목표 금액에 달성
                //개수 반환
                if (next == 0) {
                    return coinCount + 1;
                }

                //다음 노드가 0이 아니고 방문하지 않았을 때
                if (next > 0 && !visited[next]) {
                    //방문 처리
                    visited[next] = true;
                    //큐에 다음 노드와 사용 동전 개수 넣어주기
                    queue.add(new int[] {next, coinCount + 1});
                }
            }
        }
        return -1;
    }
}