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

안녕하세요, 바둑이 승차를 bfs로 풀어보다가, 시간 초과 에러가 떠서 여쭤봅니다.!

아래는 제 코드입니다.

import java.util.*;

public class Main {
    static class Node {
        int sum;
        int level;
        public Node(int sum, int level) {
            this.sum = sum;
            this.level = level;
        }
    }

    static int n;
    static int w;
    static int[] puppies;
    static int result;

    public int bfs() {
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(puppies[0]);
        Q.offer(0);
        int L = 0;
        while(!Q.isEmpty()) {
            int len = Q.size();
            if(L==n) break;
            for(int i=0 ; i<len; i++) {
                int tmp = Q.poll();
                if(tmp>w) continue;
                result = Math.max(tmp, result);
                if(L<n-1 ) {
                    int next = puppies[L+1];
                    Q.offer(tmp + next);
                    Q.offer(tmp);
                }
            }
            L++;
        }
        return result;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        w = sc.nextInt();
        n = sc.nextInt();
        puppies = new int[n];
        for(int i=0; i<n; i++) {
            puppies[i] = sc.nextInt();
        }
        T.bfs();
        System.out.println(result);
    }
}

bfs, dfs 모두 모든 노드를 방문한다는 점에서, 같을 것 같은데, 왜 bfs는 시간 초과가 날까요.?

제가 break을 놓친 부분이 있을까요?