바둑이 승차 질문입니다!

package other.study;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

import static java.lang.Integer.MIN_VALUE;
import static java.lang.Math.max;
import static java.lang.System.in;

// todo: 해결 필요!!
public class Main3 {

    static int[] ch = new int[100000000];
    static int c, n, answer = MIN_VALUE;

    public static void main(String[] args) {
        Scanner kb = new Scanner(in);

        c = kb.nextInt();
        n = kb.nextInt();
        ch = new int[n];

        int[] arr = new int[n + 1];

        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

//        DFS(0, 0, arr);
         BFS(0, arr);
        System.out.println("answer = " + answer);
    }

    static void DFS(int L, int sum, int[] arr) {

        if (sum > c) return;

        if (L == n) {
            answer = max(answer, sum);
        } else {
            DFS(L + 1, sum + arr[L], arr);
            DFS(L + 1, sum, arr);
        }
    }

    static void BFS(int L, int[] arr) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(new Node(0, arr[0]));

        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                Node tmp = Q.poll();

                if (tmp.weight > c) continue;

                if (L == n) {
                    answer = max(answer, tmp.weight);
                } else {
                    Q.offer(new Node(tmp.level + 1, tmp.weight + arr[tmp.level + 1]));
                    Q.offer(new Node(tmp.level + 1, tmp.weight));
                }

            }
            System.out.println();
            L++;
        }
    }

    static class Node {
        private int level, weight;

        public Node(int level, int weight) {
            this.level = level;
            this.weight = weight;
        }
    }
}

안녕하세요 선생님!

명품 강의 정말 잘 듣고 있어요!

바둑이 승차를 BFS로도 풀어봤는데, 문제되는 부분이 있을까해서 질문 드립니다!

늦었지만 새해 복 많이 받으세요!

안녕하세요, 인프런 AI 인턴입니다.
seon님, 자바 알고리즘 문제 해결에 도전하시는 군요! 바둑이 승차 문제를 BFS로 접근하신 것 매우 흥미롭습니다.

코드를 살펴보면, BFS 내부 로직에서 몇 가지 문제가 보입니다.

Q.offer(new Node(0, arr[0])); 부분에서 0번째 인덱스만 고려하고 있어서 시작점이 반드시 0번째 요소를 포함하게 됩니다. 이는 모든 경우의 수를 고려하지 못하기 때문에 문제가 될 수 있습니다. 그래서 초깃값으로 Q.offer(new Node(0, 0)); 와 같이 바꾸어 주어야 모든 경우를 검사할 수 있습니다.
L == n 일때 로직 처리를 위한 조건문이 현재 while문 안쪽에 있는데, 이는 한 차례 큐에서 꺼낸 뒤의 레벨을 확인하는 것이기 때문에 큐에 넣기 전에 이미 검사해야 합니다.
Node 클래스에 level을 사용하고 있지만 이는 사용되지 않고 있거나, 사용 의도가 명확하게 코드에 반영되지 않았습니다. L 변수의 값을 대신 사용하려는 것이라면, 이를 Node 객체의 생성시에 반영하여 명확하게 사용 의도를 나타내야 합니다.
BFS 함수의 매개변수인 L은 사용되고 있지 않으므로 삭제하는 것이 코드를 깔끔하게 유지하는 데 도움이 될 것입니다.

또한, DFS 방식으로 문제 해결도 시도해 보셨으면 좋겠습니다. 이미 주석 처리된 DFS 함수가 있는 것으로 보아 시도해보신 것 같네요. 이 함수를 활용하고, 제약 조건(트럭의 최대 무게를 넘지 않는 등)을 만족하도록 구현하면 해답을 찾으실 수 있을 것입니다.

BFS 방식의 수정을 예시로 들자면 다음과 같을 수 있습니다:

static void BFS(int[] arr) {
    Queue<Node> Q = new LinkedList<>();
    Q.offer(new Node(0, 0)); // 초깃값 설정 수정

    while (!Q.isEmpty()) {
        Node tmp = Q.poll();
        int L = tmp.level; // 큐에서 가져온 노드의 레벨을 사용

        if (tmp.weight > c) continue;

        if (L == n) {
            answer = max(answer, tmp.weight);
        } else {
            Q.offer(new Node(L + 1, tmp.weight + arr[L]));
            Q.offer(new Node(L + 1, tmp.weight));
        }
    }
}

수정 후에도 문제가 있다면, 다시 질문해 주세요. 그리고 새해 복 많이 받으시길 바랍니다!

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