백준 2839. 설탕 배달 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/2839

"BFS를 이용한 탐색"

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    static int N;
    static int min = -1;
    static int[] visited;
    static int[] weight = {3,5};
    static boolean ok;
    static Queue<Integer> q = new LinkedList<>();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        
        visited = new int[N+1];
        Arrays.fill(visited, Integer.MAX_VALUE);
        
        q.add(0);
        q.add(0);
        
        while(!q.isEmpty()) {
            int cnt = q.poll();
            int sum = q.poll();
            
            if(sum == N) {
                min = cnt;
                break ;
            }
            
            for (int i = 0; i < 2; i++) {
                if(sum + weight[i] > N ||visited[sum+weight[i]] <= cnt+1)
                    continue;
                
                visited[sum+weight[i]] = cnt+1;
                q.add(cnt+1);
                q.add(sum+weight[i]);
            }
        }
        System.out.println(min);
    }
 
}