[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;
    }
}

4. 게임 맵 최단거리 (BFS)

import java.util.*;

class Solution {
    public static int[] dx = {-1,1,0,0};
    public static int[] dy = {0,0,-1,1};
    
    public int solution(int[][] maps) {
        int answer = -1;
        
        int[][] visited = new int[maps.length][maps[0].length];
        
        bfs(maps, visited);
        answer = visited[maps.length-1][maps[0].length-1];
        
        return answer == 0 ? -1 : answer;
    }
    
    public void bfs(int[][] maps, int[][] visited) {
        int x = 0;
        int y = 0;
        
        visited[x][y] = 1;
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x,y});
                             
        while(!queue.isEmpty()){
            int[] current = queue.remove();
            
            int cx = current[0];
            int cy = current[1];
            
            for(int i=0; i<4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                if(nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length && visited[nx][ny] == 0 && maps[nx][ny] == 1) {
                    visited[nx][ny] = visited[cx][cy] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
}

5. 여행경로

import java.util.*;

class Solution {
    public static ArrayList<String> answers = new ArrayList<String>();
    public static boolean[] check;


    public String[] solution(String[][] tickets) {
        check = new boolean[tickets.length];

        dfs("ICN", "ICN", tickets, 0);
        Collections.sort(answers);
        return answers.get(0).split(" ");
    }

    public void dfs(String cur, String answer, String[][] tickets, int cnt) {
        if(cnt == tickets.length) {
            answers.add(answer);
            return;
        }

        for(int i=0; i<tickets.length; i++) {
            if(!check[i] && tickets[i][0].equals(cur)) {
                check[i] = true;
                dfs(tickets[i][1], answer + " " + tickets[i][1], tickets, cnt+1);
                check[i] = false;
            }
        }
    }
}