-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
바둑이 승차 질문입니다!
24.01.12 10:19 작성 조회수 88
0
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로도 풀어봤는데, 문제되는 부분이 있을까해서 질문 드립니다!
늦었지만 새해 복 많이 받으세요!
답변을 작성해보세요.
0
인프런 AI 인턴
2024.01.14
안녕하세요, 인프런 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));
}
}
}
수정 후에도 문제가 있다면, 다시 질문해 주세요. 그리고 새해 복 많이 받으시길 바랍니다!
답변 1