프로그래머스 - [Level 3] 외벽 점검(JAVA)

프로그래머스 외벽 점검[2020 카카오 블라인드]

카테고리 : 완전탐색

 모든 경우의 수를 전부 탐색하는 완전탐색이다.
하지만, 무작정 정방향, 역방향을 돌면서 탐색한다면 시간초과가 발생한다.

핵심 아이디어는 아래와 같다.
1) 순서를 고려하지 않고, 점검할 친구의 모든 조합을 만든다.

예) dist = [1,2]
[1]
[2]
[1,2]
[2,1]

2) 항상 정방향으로만 탐색한다.
출발지점에서 도착지점으로 역방향(시계반대방향)으로 점검하는 것은
도착지점에서 출발지점으로 정방향(시계방향)으로 점검하는 것과 같다.
------------------------------------
1 -> 10 (역방향)을 점검하는 것은 
10 -> 1 (정방향)을 점검하는 것과 같다.
------------------------------------
따라서, 모든 취약지점을 출발지점으로 두고, 탐색을 진행하면
모든 지점의 역방향 점검을 할 수 있다.
만약, 출발지점 -> 도착지점이 '0'을 지나친다면 도착지점은 = 도착지점 + N
이 되도록 새로운 weak 지점 배열을 만들어준다.

예) weak = [1, 5, 6, 10] , N = 12
출발지점 1 : [1, 5, 6, 10]
출발지점 5 : [5, 6, 10, 13]
출발지점 6 : [6, 10, 13, 17]
출발지점 10 : [10, 13, 17, 18]

3) 탐색을 완료한 뒤 현재 위치가 weak 배열의 마지막 원소보다 크다면
모든 취약지점 점검이 완료된 것이다.
따라서, answer 의 값을 갱신해준다.(최솟값으로)

소스 코드

import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    static boolean[] visit = new boolean[201]; 
    static ArrayList<Integer> list = new ArrayList<Integer>();
    static ArrayList<Integer> w=new ArrayList<Integer>();
    static int answer=987654321,N=0;
    static int[] d;
    
    
    void caseCheck(ArrayList<Integer> copy_w){
        int loc=copy_w.get(0);
        int idx=1;
        for(int i=0;i<list.size();i++){
            loc+=list.get(i);
            if(i<list.size()-1){
                while(loc>=copy_w.get(idx)){
                    idx++;
                    if(idx>copy_w.size()-1){
                        idx--; break;
                    } 
                }   
                loc=copy_w.get(idx);
            }
        }
        if(loc>=copy_w.get(copy_w.size()-1)) answer=Math.min(answer,list.size());
    }
    
    void check(){
        ArrayList<Integer> copy_w=new ArrayList<Integer>();
        copy_w.addAll(w);
        for(int i=0;i<w.size();i++){
            caseCheck(copy_w);
            copy_w.add(copy_w.get(0)+N);            
            copy_w.remove(0);
        }
    }
    
    void recur(int cnt){
        if(cnt>d.length) return;
        if(cnt>0) check();
        
        for(int i=0;i<d.length;i++){
            if(visit[i]) continue;
            visit[i]=true;
            list.add(d[i]);
            recur(cnt+1);
            list.remove(list.size()-1);
            visit[i]=false;
        }
    }
   
    void init(int[] weak,int[] dist,int n){
        d=dist; N=n;
        for(int i=0;i<weak.length;i++) w.add(weak[i]);
    }
    
    public int solution(int n, int[] weak, int[] dist) {
        init(weak,dist,n);
        recur(0);
        if(answer==987654321) answer=-1;
        return answer;
    }
}