[JAVA] 알고리즘 문제풀이 기초 - DFS, BFS - 기출문제

DFS, BFS 기출문제 풀이

최대점수 구하기(DFS)

• 설명 : 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
  
  

• 입력 : 첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다. 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
  
  

• 출력 :첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.
  
  

• 풀이 답안

import java.util.*;

public class Main {

    static int num, limit, score;
    static int[][] arr;

    public void DFS(int v, int sum, int curScore){

        if(sum>limit) return;
        if(score<curScore) score=curScore;
        if(v==num) return;

        DFS(v+1, sum+arr[v+1][1], curScore+arr[v+1][0]);
        DFS(v+1, sum, curScore);
    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        num = scan.nextInt();
        limit = scan.nextInt();
        arr = new int[num+1][2];
        for(int i=1; i<=num; i++){
            arr[i][0] = scan.nextInt();
            arr[i][1] = scan.nextInt();
        }
        main.DFS(0, 0, 0);
        System.out.println(score);
    }
}

• 정리
  
  • 기본 DFS 형식을 사용하되 이차원 배열을 사용하는 것이 특징
    
  • 매개변수로는 현재의 인덱스와, 합계와 현재스코어를 매개변수로 받는 형식으로 구현함