[PCCP 모의고사 1] 2번

코드

import java.util.*;

class Solution {
    int answer = 0;
    public int solution(int[][] ability) {
        
        fullScan(0,ability,new boolean[ability.length],0);

        return answer;
    }
    
    private void fullScan(int current, int[][] ability, boolean[] check,int depth) {
        if (depth == ability[0].length) {
            
            answer = Math.max(current, answer);
           
            return;
        }
        
        for (int i=0;i<ability.length;i++) {
            if (!check[i]) {
                check[i]=true;
                fullScan(current+ability[i][depth],ability,check,depth+1);
                check[i]=false;
            }
        }
    }
}

풀이

🥳문제 조건을 보시면 ability의 크기가 매우 작은 것을 확인 할 수 있습니다. 이를 이용하여 완전탐색을 하면 된다는 생각이 들어 dfs를 이용하여 풀어보았습니다. (백트랙킹)
단 완전 탐색을 하되 이미 check한 곳은 다시 check하지 않도록 하기 위해 boolean[]을 이용하여 처리를 하였습니다.

출처: 프로그래머스 - 코딩테스트