[프로그래머스] Lv.2 완전범죄 java 중복제거 dfs

https://school.programmers.co.kr/learn/courses/30/lessons/389480#qna

프로그래머스

시간초과 dfs

쌩 dfs(깊이우선탐색)로 풀었더니 시간초과가 나서 40점이 나왔다. 방문 여부를 확인하지 않고 깊이를 index +1 해 다음 으로 넘어가도록 했다. 

시간초과 이유는 인덱스가 하나씩 증가할 때마다 2개의 dfs가 생긴다. (a가 훔치는 경우, b가 훔치는 경우)

2^n 최대 info길이가 40이니까 -> 시간복잡도가 2^40 이 된다. 

//dfs
class Solution {
    int aMin = Integer.MAX_VALUE;
    public int solution(int[][] info, int n, int m) {
        
        dfs(info, 0, 0, 0, n, m);
        if(aMin >= n) return -1;
        
        return aMin;
    }
    
    public void dfs(int[][] info, int index, int aWeight, int bWeight, int n, int m){
        if(index == info.length){
          if(bWeight < m && aWeight < n){
                aMin = Math.min(aMin, aWeight);
            }
            return;
        }
            
        if(aWeight+info[index][0] < n){
            dfs(info, index+1, aWeight+info[index][0], bWeight, n, m);
        }
        if(bWeight+info[index][1] < m){
            dfs(info, index+1, aWeight, bWeight+info[index][1], n, m);
        }
    }
}

 

중복제거 dfs

시간을 어떻게 줄이지 찾아보다가 똑같은 dfs인데 중복을 제거하는 방법을 봤다.

처음에는 같은 조합이 되는 경우가 없으니까 중복되는 게 없다고 생각했는데 깨달았다.. 중복이 된다는 것

a와 b의 누적값으로 탐색을 계속 진행하기 때문에 어떠한 상태는 중복이 될 수 있는 것이다.

예를 들어 순서가 aTrace, bTrace, index 라고 하면
어느순간 3, 5, 4 이 되었을 때 이후 일어나는 경우의 수 = 과거  3, 5, 4 이후 일어난 경우의수
로 같기 때문에 이전 상태를 다시 탐색하지 않도록 체크해줘야 한다. 

그래서 Set에 문자열로 aTrace + "," + bTrace + "," + index 인 상태값을 넣어 방문했던 상태를 체크해 해결할 수 있다. 

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int[][] info;
    public int n, m;
    public int aMin = Integer.MAX_VALUE;
    
    public int solution(int[][] info, int n, int m) {
        int answer = 0;
        this.info = info;
        this.n = n;
        this.m = m;
        
        Set<String> visited = new HashSet<>();
        dfs(0, 0, 0, visited);
        if(aMin >= n) return -1;
        return aMin;
    }
    public void dfs(int aTrace, int bTrace, int index, Set<String> visited){
        if(index == info.length){
            if(aTrace < n && bTrace < m){
                aMin = Math.min(aMin, aTrace);
            }
            return;
        }
        
        String str = aTrace + "," + bTrace + "," + index;
        if(visited.contains(str)){
            return;
        }
        visited.add(str);
        
        if(aTrace + info[index][0] < n){
            dfs(aTrace + info[index][0], bTrace, index+1, visited);
        }
        if(bTrace + info[index][1] < m){
            dfs(aTrace, bTrace + info[index][1], index+1, visited);
        }
    }
}