[Algorithm] 프로그래머스 DFS/BFS (Java)

1. 타겟 넘버

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }    
    
    public int dfs(int[] numbers, int target, int count, int sum) {
        
        if(count == numbers.length) {
            if (sum == target) {
                return 1;
            }
            return 0;
        }
        
        return dfs(numbers, target, count + 1, sum + numbers[count]) + dfs(numbers, target, count + 1, sum - numbers[count]);
    }
}

• dfs 보다는 동적 계획법에 가까운 풀이법...

-arr[0] -arr[1]
        +arr[0]

+arr[0] -arr[1]
        +arr[0] ...

• 이런식으로 분기 처리를 해 나가면서 모든 경우의 수를 구하는 방법!

2. 네트워크

class Solution {
    public int solution(int n, int[][] computers) {
        int count = 0;
        boolean[] check = new boolean[n];
        
        for(int i=0; i<computers.length; i++) {
            if(!check[i]) {
                count++;
                dfs(computers, i, check);
            }
        }
        
        return count;
    }
    
    public void dfs(int[][] computers, int idx, boolean[] check) {
        check[idx] = true;
        
        for(int i=0; i<computers.length; i++) {
            if(!check[i] && computers[idx][i] == 1 && i != idx) {
                dfs(computers, i, check);
            }
        }
    }
}

3. 단어 변환

class Solution {
    public static boolean[] check;
    public static int answer = 51;
    
    public int solution(String begin, String target, String[] words) {
        check = new boolean[words.length];
        
        dfs(begin, target, words, 0);
        
        return answer == 51 ?  0 : answer;
        // 51 : 배열 최대 길이 50, 변환할 수 없다면 answer가 설정한 값에서 변하지 않음 (그대로 51)
    }
    
    public void dfs(String begin, String target, String[] words, int cnt) {
        if (begin.equals(target)) {
            answer = Math.min(answer, cnt);
            return;
        }
        
        for(int i = 0; i<words.length; i++) {
            if(!check[i] && differ(begin, words[i])) {
                check[i] = true;
                dfs(words[i], target, words, cnt+1);
                check[i] = false;
            }
        }
    }
    
    public boolean differ(String begin, String compare) {
        int cnt = 0;
        
        for(int i=0; i<begin.length(); i++) {
           if(begin.charAt(i) != compare.charAt(i)) cnt++;
        }
            
        return cnt == 1 ? true : false;
    }
}